12983. Najdłuższy spójny podciąg ciągu binarnego [AL_03_02]

Zadanie:
https://pl.spoj.com/problems/AL_03_02

Skrócony opis problemu:

Dla podanego ciągu binarnego (składającego się tylko z 0 i 1) o długości $n$, znaleźć długość najdłuższego spójnego podciągu zawierającego maksymalnie $k$ jedynek.

Rozwiązanie naiwne:

Sprawdzamy dla każdego spójnego podciągu ile zawiera jedynek. Jeśli ilość jedynek jest mniejsza lub równa $k$ to aktualizujemy wynik jeśli długość nowo-znalezionego podciągu jest większa niż stary wynik.

Złożoność: $O(n^2)$, bo ilość spójnych podciągów w ciągu o długości $n$ wynosi $\frac{n(n+1)}{2}$.

Rozwiązanie sprytne:

Tylko ilość jedynek jest ograniczona. Ilość zer jest dowolna. Możemy zatem połączyć wszystkie zera w jedną liczbę będącą ilością tych zer.

Np. dla ciągu: 101000011100100 możemy go zamienić na: "x 1 x 4 xxx 2 x 2".

Idziemy więc od lewej strony i jeśli napotkamy 0 to inkrementujemy zmienną $x$ (która na początku jest równa 0). W $x$ będzie tymczasowa długość podciągu, który ma $\le k$ 1nek.

Jeżeli napotkamy 1nkę i $y < k$ (gdzie $y$ to ilość jedynek, które zużyliśmy), to inkrementujemy $x$ i $y$ i zapisujemy w tablicy $tab$ indeks tej jedynki.

Ostatnia sytuacja to taka, że mamy 1nkę i $y=k$. Nie możemy sobie wtedy pozwolić na dodanie nowej 1nki. Sprawdzamy więc czy $x > max$ (w $max$ trzymamy nasz ostateczny wynik) i jeśli tak to aktualizujemy $max$. Następnie aktualizujemy $x=i-tab[start++]$. W $tab[start]$ jest indeks pierwszej 1nki, która jest zawarta a naszym ciągu. Jeśli chcemy ją wyrzucić (chcąc dodać nową jedynkę) to musimy wyrzucić też wszystkie zera przed nią. Tak więc długość podciągu z nową 1nką to różnica między indeksami tych dwóch 1nek. $start++$ oznacza, że wyrzuciliśmy 1nkę z początku ciągu. Na koniec warunku musimy jeszcze tylko dodać nową 1nkę do tablicy: $tab[end++]=i$.

Po wczytaniu całego ciągu musimy jeszcze raz porównać $x$ i $max$ (bo sprawdzamy to tylko gdy przekroczymy ilość 1nek). Na koniec wypisujemy $max$.

Złożoność: $O(n)$, bo przechodzimy cały ciąg tylko raz i dla każdego elementu wykonujemy stałą ilość instrukcji.

Ostateczny algorytm:

int main()
{
    int n, k, i, x, y, max, start, end, tab[n];
    char z;

    get(n, k);
    max = x = y = start = end = 0;
    for(i = 0; i < n; ++i)
    {
        get(z);
        if(z == '0')
            ++x;
        else if(y < k)
            ++x,
            ++y,
            tab[end++] = i;
        else
        {
            if(x > max)
                max = x;
            x = i-tab[start++];
            tab[end++] = i;
        }
    }
    if(x > max)
        max = x;
    print(max);
}