== include(page="template/taskheader" task_id="podm") ==

Se dă un produs matricial $M = M{~1~}M{~2~}...M{~n~}$. Cum înmulţirea matricelor este asociativă, toate parantezările conduc la acelaşi rezultat. Însă, numărul total de înmulţiri scalare al produsului matricial poate să difere substanţial în funcţie de ordinea efectuării calculelor, ordine dată de paranteze. Dimensiunile celor $n$ matrici se dau sub forma unui şir $d$ astfel încât perechea $(d{~i-1~}, d{~i~})$ reprezintă dimensiunile matricii $M{~i~}$.

Se dă un produs matricial $M = M{~1~}M{~2~}...M{~n~}$. Rezultatul înmulţirii matricilor poate să difere în funcţie de ordinea efectuării calculelor, ordine dată de paranteze. Dimensiunile celor $n$ matrici se dau sub forma unui şir $d$ astfel încât perechea $(d{~i-1~}, d{~i~})$ reprezintă dimensiunile matricii $M{~i~}$.

h2. Cerinţă

Se cere să se minimizeze numărul total de înmulţiri scalare al lui $M$, valoare ce corespunde unei parantezări optime a produsului matricial.

Se cere să se determine valoarea minimă a lui $M$, valoare ce corespunde unei parantezări optime a produsului matricial.

h2. Date de intrare

Fişierul de intrare $podm.in$ conţine pe prima linie un număr natural $n$, reprezentând numărul matricelor. Pe următoarea linie se găsesc $n + 1$ numere naturale, reprezentând valorile şirului $d$.

Fişierul de intrare $podm.in$ conţine pe prima linie un număr natural $n$, reprezentând numărul matricilor. Pe următoarea linie se găsesc $n + 1$ numere naturale, reprezentând valorile şirului $d$.

h2. Date de ieşire

În fişierul de ieşire $podm.out$ se va găsi un singur număr natural egal cu valoarea minimă a numărului total de înmulţiri scalare a produsului matricial $M$.

În fişierul de ieşire $podm.out$ se va găsit un singur număr natural egal cu valoarea minimă a lui $M$.

h2. Restricţii