Problema bradut, etapa 9

[•nparfene2004]

As dori si eu o indicatie la problema bradut de la grupa large, etapa 9 campion.

Eu m-am gandit asa:
Notam a[i,j] = numarul de posibilitati de a pune pe primele i nivele j cutii verzi.
Problema e ca nu am memorie suficienta pentru ca j este mare.

O idee mai buna imi dati si mie? Multumesc!

[•andrei-alpha]

E buna ideea, la dinamica ai nevoie sa retii doar ultima linie si cum j este maxim 100 000 inseamna doar 0.4 Mb memorie.

[•Mishu91]

Ideea ta e bună, dar este posibil să nu intre în memorie întreaga matrice. De aceea, poți considera doar ultimele 2 rânduri (se observă că nu ai nevoie de mai mult), sau mai simplu, poți ține dinamica a[ i ] -> numărul de posibilități de a pune i cutii verzi, pentru că ordinea în care acestea se pun nu este relevantă.