* @dp[i] = costul minim de a acoperi primele i intervale.@

Parcurgem pozitiile de pe axa Ox de la stanga la dreapta. Presupunem ca stim configuratia de intervale la care suntem la pozitia i. Aceasta va fi o secventa continua de intervale - [l..r], unde l este cel mai din stanga interval iar r este cel mai din dreapta. intervalele [1..l-1] trebuiau acoperite cu pozitii mai mici decat aceasta, nu mai avem cum sa le acoperim de aici. Asadar, este necesar si suficient sa updatam @dp[k] = min (dp[k], dp[l-1] + v[i])@ pentru orice l ≤ k ≤ r. Mai jos aveti codul pentru a intelege mai bine:

Parcurgem pozitiile de pe axa Ox de la stanga la dreapta. Presupunem ca stim configuratia de intervale la care suntem la pozitia i. Aceasta va fi o secventa continua de intervale - [l..r], unde l este cel mai din stanga interval iar r este cel mai din dreapta. intervalele [1..l-1] trebuiau acoperite cu pozitii mai mici decat aceasta, nu mai avem cum sa le acoperim de aici. Asadar, este necesar si suficient sa actualizam @dp[k] = min (dp[k], dp[l-1] + v[i])@ pentru oricare k cu l ≤ k ≤ r. Mai jos aveti codul pentru a intelege mai bine:

== code(cpp) |
int get_answer (vector<pair<int,int> > intervals)

* dp[i][j] = valoarea maxima a unei livezi care contine celula (i,j) si poate contine celule de pe linii ≤ i.

O rezolvare in <tex>O(N*M^3^)</tex> este destul de la indemana. Parcurgem liniile de la 1 la i. Presupunand dinamica calculata pentru liniile &l; i

O rezolvare in <tex>O(N*M^3^)</tex> este destul de la indemana. Parcurgem liniile de la 1 la N. Presupuem dinamica calculata pentru liniile < i. Atunci, la linia i, fixam fiecare subsecventa de coloane (j,k) j &le; k si actualizam in felul urmator:
 
* Fie @s(i,j,k) = dp[i][j] + dp[i][j+1] + ... + dp[i][k]@
* Fie @mv(i,j,k) = max(dp[i][j], dp[i][j+1],..., dp[i][k])@
* Atunci actualizam dp[i][h] = max(dp[i][h], s(i,j,k) + mv(i-1,j,k)) oricare h cu j &le; h &le; k
 
Calcularea lui s, mv precum si actualizarea se pot parcurcand de la j la k, complexitatea finala fiind cea mentionata mai sus.
 
Vrem sa coboram complexitatea la <tex>O(N*M^2^)</tex>. Valorile lui s si mv sunt usor de obtinut in O(M^2^) per linie parcurgand subsecventele

==include(page="onis-2015/solutii-runda-1/meciul")==