|
Titlul: Problema bradut, etapa 9 Scris de: Parfene Narcis din Martie 01, 2010, 11:58:28 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! Titlul: Răspuns: Problema bradut, etapa 9 Scris de: Andrei-Bogdan Antonescu din Martie 01, 2010, 12:49:03 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.
Titlul: Răspuns: Problema bradut, etapa 9 Scris de: Andrei Misarca din Martie 01, 2010, 18:34:57 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ă.
|