zbyt wolne dp

Question

siema, wzialem sie dzisiaj za cwiczenie dp i podjalem sie proby zrobienia zadania: https://szkopul.edu.pl/problemset/problem/ky4uF8wdhvqLQAkPtt1wI-_5/site/?key=statement

niestety dp, ktorego uzylem jest zbyt wolne. pomoze ktos, albo wskaze gdzie robie za duzo operacji?

kod: https://ideone.com/pEsxiN

Comments

Ale dobrze rozumiem, że wynik może być maks 3, bo wszystkie liczby są z zbioru 0,1,2?

---

tak, czyli mamy przypadki:

{0}, {0, 1}, {0, 1, 2}, {0, 2}, {1}, {1, 2} {2}

Answer 1

Tutaj skoro masz tylko tyle liczb, to nie musisz robić żadnego dp, a mianowicie:

Masz 3 przypadki:

L[i] i-ta liczba z wyjścia

 - jeśli L[i] = 0, to wyn = max(wyn,1), bo nie podbijesz tej jedynki nigdzie w lewo,bo nie możesz np 0, 0, albo -1, 0.

- jeśli L[i] = 1, to jeśli wcześniej było jakieś zero(musisz mieć flagę bool czy_bylo_zero) i jeśli było, to wyn = max(wyn,2), a jak nie to wyn = max(wyn,1), bo nigdy na lewo nie podbijesz tej jedynki.

- jeśli L[i] = 2, to musisz mieć zmienną max_wyn_dla_jedynki, na początku -1, i jeśli max_wyn_dla_jedynki = -1 (nie było wcześniej jedynki, jeśli masz L[i] = 1, to max_wyn_jedynki = max(max_wyn_jedynki, to co sprawdzaliśmy, gdy L[i] = 1), to sprawdzasz czy było wczesniej zero. Jak było, to wyn = max(wyn,2), jak nie to wyn = max(wyn,1). A natomiast, jeśli max_wyn_dla_jedynki != -1, to wyn = max(wyn, max_wyn_dla_jedynki+1)

I dostajesz rozwiąnie O(N), i pamięć O(1)

I na koniec  zwracasz wyn.

Ciekawszy jest problem szukania najdłuższego podciągu rosnącego, jak liczby są dowolne. Wtedy robisz faktycznie dp.

dp[i] = max z wszystkich dp wcześniejszych, gdzie L[i] > L[j], taki naiwny algorytm ma O(N^2), a można zrobić w O(N lg N), korzystając z drzewa przedziałowego przedział-punkt, gdzie klucze to wartości, a wyniki w drzewie, to max dp dla danej wartości. Popatrz sobie na zadanie Sponsor z 1 OI, jest też na forum.

https://szkopul.edu.pl/problemset/problem/E3eS485F0Qmr6RLduybh_e5b/site/?key=statement

Comments

właśnie chwile po napisaniu posta zdalem sobie z tego sprawe i napisalem cos takiego:

#include <bits/stdc++.h>

using namespace std;

int n, arr[1000001], mx = 0;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;

    for (int i = 1; i <= n; i ++)
        cin >> arr[i];

    bool zer = 0, jed = 0, dwa = 0;
    for (int i = 1; i <= n; i ++) {
        if (arr[i] == 0)
            zer = 1, mx = max(mx, 1);
        else if (arr[i] == 1) {
            jed = 1;
            mx = max(mx, 1);
            if (zer == 1)
                mx = max(mx, 2);
        }
        else {
            dwa = 1;
            mx = max(mx, 1);
            if (jed == 1) {
                mx = max(mx, 2);
                if (zer == 1)
                    mx = max(mx, 3);
            }
            if (zer == 1)
                mx = max(mx, 2);
        }
    }

    cout << mx;
}

 

---

a to daje dobre wyniki?

---

od 10 minut nie wypluwa mi rozwiazania. chyba szkopul sie zacial

---

Mi się ten kod wydaje trochę podejrzany

---

nie daje mi 100%, tylko 60

---

Tak właśnie myślałem popatrz na 21 linie dajesz jeden na 1, a co jeśli było wcześniej 0?

A dwie linie pozniej robisz wyn z 2, a nie jeden.

---

wiesz, co chyba blad jest w tym, ze jesli arr[i] == 0 to musze wyzerowac jed i dwa. Bo gdy tego nie robie, to dla testu:

3

1 0 2

wypluwa mi 3, a powinno 2.

Analogicznie jesli odwiedzam 1 musze wyzerowac dwa.

---

i rzeczywiscie, teraz daje mi 100%. Tutaj kod:

#include <bits/stdc++.h>

using namespace std;

int arr[1000001];

int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	int n;
	cin >> n;

	for (int i = 1; i <= n; i ++)
		cin >> arr[i];

	bool zer = 0, jed = 0, dwa = 0;
	int mx = 0;
	for (int i = 1; i <= n; i ++) {
		if (arr[i] == 0) {
			zer = 1, jed = 0, dwa = 0;
			mx = max(mx, 1);
			
		}
		else if (arr[i] == 1) {
			jed = 1, dwa = 0;
			mx = max(mx, 1);
			
			if (zer == 1)
				mx = max(mx, 2);
		}
		else {
			dwa = 1;
			mx = max(mx, 1);

			if (jed == 1) {
				mx = max(mx, 2);

				if (zer == 1)
					mx = max(mx, 3);
			}
			if (zer == 1)
				mx = max(mx, 2);
		}
	}

	cout << mx;
}

 

---

Super, że przeszło. Całkiem możliwe, nie wglębiałem się w twój kod szczegółowo.