Problema 2 – expresie - 100p – clasele XI-XII

Vom construi un arbore al expresiei in felul urmator: fiecare operator va avea asociat un nod intern, iar fiecare numar un nod frunza. Un nod care contine un operator poate avea oricati fii (spre deosebire de exact 2 la arborele clasic) pentru a trata cazurile care folosesc asociativitatea operatorilor. Pentru o expresie de tipul (a1 op a2 op … op an) maximala (nu poate fi extina la stanga / dreapta cu operatorul op), pentru care operatorul op este asociativ, arborele arata in felul urmator:

* insert image here *

unde nodurile a1, a2, …, an reprezinta arborii corespunzatori expresiilor.
Se observa ca arborele construit astfel este unic pentru o expresie.

Solutia este sa calculam urmatoarea dinamica: dp[node] = numarul de moduri de a evalua expresia corespunzatoare subarborelui cu radacina in nodul node.

Aratam mai intai cum aflam raspunsul daca radacina are 2 fii. Presupunem ca expresia din primul fiu poate fi evaluata in x moduri si contine a operatori, iar cea din al doilea fiu in y moduri si contine b operatori. Evident nu putem evalua operatorul din radacina pana cand nu am evaluat ambele expresii din fii. Avem x*y moduri de alege modurile de evaluare pentru cei doi fii si C(a+b,a) moduri de a interclasa operatiile efectuate, unde C(n,k) reprezinta combinari de n luate cate k.

Consideram acum cazul general, cand radacina are n fii. Vom construi o alta dinamica: nr[i][j], numarul de moduri de a evalua expresia formata din fiii i, i+1, …, j, adica (ai op ai+1 op …,op aj). Raspunsul va fi nr[0][n-1]. Pentru a rezolva aceasta dinamica, fixam k cu semnificatia ca expresia va fi evaluata astfel:  (ai op ai+1 op …,op ak) op (ak+1 op …,op aj). Pentru un k fixat, avem nevoie de valorile nr[i][k], nr[k+1][j], de numarul de operatori din expresiile din cele doua paranteze (se pot mentine in dinamica), iar combinarea lor se face ca in cazul cu radacina cu 2 fii. Facand suma pentru k=i, i+1,…,j-1, obtinem nr[i][j].

Complexitate:
Pot exista cel mult m noduri, unde este lungimea expresiei, iar fiecare dinamica se afla in , unde n este numarul de noduri fii, complexitatea este (fiecare nod ‘participa’ la cel mult o dinamica).

PS. o sa incerc sa arat ca in cel mai rau caz sunt operatii, deci ar trebui sa intre intr-o secunda.