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^)$}.