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

Raspunsul va fi max dintre toate dp[i][j].
 

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.

Calcularea lui s, mv precum si actualizarea se pot face parcurgand 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^) pe linie parcurgand subsecventele de coloane in modul corespunzator. Problema este cum actualizam ? Vom utiliza o dinamica auxiliara independenta de linii (care se refera doar la o singura linie la un moment dat).
 
* pe linia i, @auxdp[j][k] = valoarea minima a lui dp[i][h] cu h intre j si k.@
 
Definitia ne ajuta mai putin sa intelegem functionalitatea acestei dinamici. Ce facem cu ea este ca atunci cand am calculat s(i,j,k) + mv(i-1,j,k) pentru o subsecventa (j,k) in loc sa facem un _for_ de la j la k, incarcam valoarea in @auxdp[j][k]@. Dupa ce am parcurs toate subsecventele, facem actualizari in auxdp in felul urmator:
 
* auxdp[j+1][k] = max (auxdp[j+1][k], auxdp[j][k]) cu j < k
* auxdp[j][k-1] = max (auxdp[j][k-1], auxdp[j][k]) cu j < k
 
^ Observam ca aici subsecventele trebuie parcurse in ordinea inversa a lungimii. La final, valoarea lui dp[i][j] se va afla nicaieri altundeva decat in auxdp[j][j]. Ce am facut practic a fost sa acumulam actualizarile in aceasta dinamica iar apoi sa le "impingem spre interior" catre punctele singulare, acelea fiind singurele valori de care avem nevoie mai departe.

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

Exista si alte moduri de a face reducerea la <tex>O(N*M^2^)</tex>. Unii dintre voi le-ati aplicat in timpul concursului. Va invitam sa va ganditi la ele.

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