Solutia problemei Picazo

Se observa faptul ca Picazo nu va cumpara niciodata aceeasi culoare si ca nu va picta de doua ori aceeasi celula.

Solutia O(2^N * (N + Q))

Incercam toate variantele si luam maximul.

Solutia O(N²)

Calculam bonus[i] = numarul de intervale care il contin pe i. Costul final pentru o configuratie este suma de bonus[i] - k pentru toate i-urile pictate + cate intervale contin cel putin o pozitie nepictata

De aici ne vine ideea sa folosim dinamica:
dp[i][j] = profitul maxim daca am rezolvat prefixul de lungime i unde ultima pozitie nepictata este j iar i + 1 este si el nepictat.
Acum avem recurentele

• dp[i][i] = max(dp[i - 1][j]) + numar de intervale care incep pe (i + 1) [j < i]
• dp[i][j] = dp[i - 1][j] + (bonus[i] - k) + numar de intervale care incep pe (i + 1) [j < i]

Insa recurenta nu este inca perfecta deoarece cand am pictat pozitia i s-au dezactivat niste intervale. Asa ca vom trece prin toate intervalele cu capatul dreapta in i si vom scadea 1 din toate dp[i][j] pentru care j < capatul stanga al lor.

Solutia O(N * logN)

Se observa ca putem folosi un arbore de intervale pentru a simula operatiile de la solutia precedenta