Nu aveti permisiuni pentru a descarca fisierul grader_test7.in
Diferente pentru onis-2015/solutii-runda-1 intre reviziile #69 si #68
Nu exista diferente intre titluri.
Diferente intre continut:
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 ≤ k si actualizam in felul urmator:
*Definim@s(i,j,k) = dp[i][j] + dp[i][j+1] + ... + dp[i][k]@ *Definim@mv(i,j,k) = max(dp[i][j], dp[i][j+1],..., dp[i][k])@
* 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 ≤ h ≤ k Calcularea lui s, mv precum si actualizarea se pot face parcurgand de la j la k, complexitatea finala fiind cea mentionata mai sus.
