h3. PetSoft

In fiecare nod din arbore vom retine doua valori $A{~i~}{~0~}$ = costul minim pentru a cupla subarborele cu radacina in {$i$}, fara a cupla nodul $i$ cu cineva, si $A{~i~}{~1~}$ acelasi lucru, dar cupland nodul $i$ cu cineva. Pentru a calcula aceste valori in fiecare nod, luam numerele de ordine a fiilor, le sortam si aplicam o alta dinamica pentru a obtine echipe cu cost maxim. Astfel determinam {$A{~i~}{~0~}$}. Pentru a calcula {$A{~i~}{~1~}$}, inseram si nodul $i$ in lista fiilor, sortam din nou si aplicam aceeasi dinamica (atentie la detalii de implementare!). Dinamica se face astfel: retinem in $C{~i~}{~j~}$ = costul maxim pentru a forma echipe de cost maxim cu valorile de pe pozitiile {$i, i+1 ... j-1, j$}. Este evident ca $C{~i~}{~j~}$ se obtine din {$C{~i+1~}{~j~}$}, $C{~i~}{~j-1~}$ si {$C{~i+1~}{~j-1~}$}. Complexitatea finala este {$O(N^2^)$}.

In fiecare nod din arbore vom retine doua valori A[i][0] = costul minim pentru a cupla subarborele cu radacina in i, fara a cupla nodul i cu cineva, si A[i][1] acelasi lucru, dar cupland nodul i cu cineva. Pentru a calcula aceste valori in fiecare nod, luam numerele de ordine a fiilor , le sortam si aplicam o alta dinamica pentru a obtine echipe cu cost maxim. Astfel determinam A[i][0]. Pentru a calcula A[i][1], inseram si nodul i in lista fiilor, sortam din nou si aplicam aceeasi dinamica (atentie la detalii de implementare!). Dinamica se face astfel: retinem in C[i][j] = costul maxim pentru a forma echipe de cost maxim cu valorile de pe pozitiile i, i+1...j-1, j. Este evident ca C[i][j] se obtine din C[i+1][j], C[i][j-1] si C[i+1][j-1]. Complexitatea finala este O(N^2).
 
References
 
Visible links
1.