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] como dp_{i,j}, al principio dp_{i,i} = 0, después podemos unir dos rangos [i,k] y (k,j], o sea, actualizar 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, ya sea recursiva o iterativamente en O(n^3).


Comments

There are no comments at the moment.