Scrie aici despre grigore-moisil-2009/solutii/cuburi3

h2(#cuburi3). 'Cuburi3':problema/cuburi3

Vom prezenta trei soluţii, toate aplicând metoda $programării dinamice$, prima fiind una cu _memoizare_, a doua una clasică iar a treia folosind '_arbori indexaţi binar_':http://www.topcoder.com/tc?module=Static&d1=tutorials&d2=binaryIndexedTrees.

* sortăm crescător greutăţile cuburilor, eliminăm duplicatele obţinând un vector de lungime $lung$;
* căutăm în acest vector cu algoritmul căutării binare greutatea curentă $g{~i~}$, găsind-o pe o poziţie $p$;

* interogăm AIB-ul pe intervalul $[p, lung]$ pentru a determina $max { bst{~j~} : 1 &ge; j < i şi g{~j~} &ge; g{~i~}}$, ştiind că o interogare într-un AIB are complexitatea $O(log n)$;

* interogăm AIB-ul pe intervalul $[p, lung]$ pentru a determina $max { bst{~j~} : 1 &le; j < i şi g{~j~} &ge; g{~i~}}$;

* actualizăm în AIB intervalul $[1, p]$ cu $bst{~i~}$.

 
Operaţiile de interogare şi actualizare într-un AIB au complexitatea $O(log(n))$.