Editorial for Slimes

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: humbertoyusta

Denotemos a la mejor respuesta para el rango $[i,j]$ ~[i,j]~ como $dp_{i,j}$ ~dp_{i,j}~, al principio $dp_{i,i} = 0$ ~dp_{i,i} = 0~, después podemos unir dos rangos $[i,k]$ ~[i,k]~ y $(k,j]$ ~(k,j]~, o sea, actualizar $dp_{i,j}$ ~dp_{i,j}~ con $dp_{i,k} + dp_{k+1,j} + sum(j) - sum(k) + sum(k) - sum(i-1)$ .

De esta forma podemos resolver el problema con $dp$ ~dp~, ya sea recursiva o iterativamente en $O(n^3)$ ~O(n^3)~.

Comments

There are no comments at the moment.