245 Avere

[•filipb]

Aici puteţi discuta despre problema Avere.

[•dornescuvlad]

Salut, am o solutie in O(S^3) care ia maxim 50 puncte (cu tot cu reconstituire).Am nevoie de un hint pentru modul in care reprezint tabloul de PD (si complexitate mai mica, O(S^2) ma gandesc).
Eu am DP[ i ][ j ] - nr.de posibilitati, a.i sa formez suma i si cu ultimul element ales j.
Solutia mea e suma de pe linia n.
Mersi.  

L.E : Am citit si solutia oficiala de la 'Avere - clasa a X-a, ONI 2005'.Problema e ca nu inteleg ce inseamna c[ i ][ j ] la ei, pentru ca e scrisa doar o recurenta, fara a fi explicata starea.

[•pauldb]

Merge sa reduci recurenta la dinamica ta la O(1) folosind sume partiale.