infoarena informatica de performanta

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.

Varianta 1

Vom arăta că soluţia are structură optimă: presupunem că turnul de cuburi format din cuburile numerotate cu p₁, p₂, ..., p_k în această ordine are înălţime maximă. Acum turnul de cuburi format din cuburile p₂, ..., p_k este cel mai înalt turn care îl are la bază pe p₂. Dacă ar exista turn mai înalt care la bază să îl aibă tot pe p₂, atunci acesta s-ar putea aşeza pe p₁ şi astfel am obţine un turn mai înalt decât cel din presupunerea iniţială. Am afirmat că acel ipotetic turn mai înalt care începe cu p₂ l-am aşeza pe p₁, deoarece p₁ nu poate să apară în acest turn care începe cu p₂, ţinând cont de proprietăţile turnului.

Descompunem problema în subprobleme: pentru orice i (1 ≤ i ≤ n) trebuie să determinăm înălţimea maximă a turnului care la bază îl are pe cubul i. Fie bst_i turnul de înălţime maximă ce se termină pe poziţia i.

• bst_i = max { bst_j : 1 ≤ j ≤ n, i != j şi g_j ≤ g_i şi l_j ≤ l_i } + l_i

Vom determina soluţia optimă recursiv şi vom păstra rezultatele subproblemelor, de unde le vom citi dacă în continuare va fi nevoie de ele. Şirul care memorează rezultatele subproblemelor se iniţializează cu 0, pentru a şti dacă elementul respectiv s-a calculat deja sau nu.

Algoritmul lucrează în O(n²), şi are nevoie de Θ(n) memorie.

Varianta 2

O altă soluţie având complexitatea O(n²) se poate obţine sortând cuburile descrescător după lungimea laturii şi în caz de egalitate după greutate. După sortare putem aplica metoda programării dinamice în felul următor:

• bst_i – înălţimea celui mai înalt turn ce se poate construi în aşa fel încât ultimul cub să fie cubul i.

Sortarea ne garantează că cubul i se poate aşeza doar pe cuburi având indice mai mic. Astfel recurenţa va fi:

• bst_i = max { bst_j : 1 ≤ j < i şi g_j ≥ g_i} + l_i

Soluţia se va afla în elementul maxim din bst. Pentru a putea reconstrui soluţia, trebuie reţinut pentru fiecare i, acel j prin care s-a obţinut maximul pentru bst_i.

Varianta 3

Folosind arbori indexaţi binar (notat în continuare cu AIB), vom obţine un algoritm de complexitate O(n log n) care necesită Θ(n) memorie. Deoarece cerinţa problemei este de a construi un subşir (g₁, l₁), (g₂, l₂), ..., (g_k, l_k) astfel încât g₁ ≥ g2 ≥ ... ≥ gk şi l₁ ≥ l₂ ≥ ... ≥ l_k, întâi sortăm descrescător cuburile în funcţie de lungimea laturii, iar în caz de egalitate, descrescător în funcţie de greutate.

Pentru poziţia i vom alege bst_j maxim, astfel încât greutatea cubului j, j < i, să fie mai mare sau egală cu greutatea cubului i. Observăm că j < i este echivalent cu l_j ≥ l_i, adică condiţia lungimilor laturilor este îndeplinită. Însă, noi avem nevoie doar de greutăţile mai mari sau egale decât greutatea curentă g_i. Aici intervine AIB, în felul următor:

• 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 ≤ j < i şi g_j ≥ 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)).