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

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~}$.

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~}$.

h2. Cerinţă

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

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

h2. Date de intrare

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$.

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$.

h2. Date de ieşire

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

Î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$.

h2. Restricţii

h2. Aplicaţii

Parantezarea optimă de matrici este o aplicaţie clasică a metodei _programării dinamice_ ce doreşte a ilustra principiul construcţiei unui tablou diagonală cu diagonală. Pentru a vă însuşi această tehnică vă recomand să rezolvaţi următoarele probleme:

Parantezarea optimă de matrici este o aplicaţie clasică ce ilustrează cele două caracteristici care permit o rezolvare folosind _metoda programării dinamice_: substructură optimală, suprapunerea subproblemelor. Pentru a vă însuşi această tehnică vă recomand să rezolvaţi următoarele probleme:
* 'Redu':problema/redu

* 'Recycling':http://icpcres.ecs.baylor.edu/onlinejudge/index.php?option=com_onlinejudge&Itemid=8&category=27&page=show_problem&problem=2518, _UVa_
* 'Stiva':problema/stiva, _Baraj ONI, 2008_

* 'Expresii algebrice':problema/expresii
* "Game Po":http://acm.sgu.ru/problem.php?contest=0&problem=273, _SGU_

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

4318