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

Poveste şi cerinţă...

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

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

Î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

* $... ≤ ... ≤ ...$

* $1 ≤ n ≤ 500$
* $1 ≤ d{~i~} ≤ 10 000$, unde $0 ≤ i ≤ n$

h2. Exemplu
table(example). |_. podm.in |_. podm.out |

| This is some
  text written on
  multiple lines.
| This is another
  text written on
  multiple lines.

| 4
13 5 89 3 34
| 2856

|
h3. Explicaţie

...

În exemplu se dau $4$ matrici: $A$ de dimensiuni $(13, 5)$, $B$ de $(5, 89)$, $C$ de $(89, 3)$, $D$ de $(3, 34)$. În funcţie de ordinea efectuării înmulţirilor matriciale , numărul total de înmulţiri scalare poate să fie foarte diferit:
 
* $(((AB)C)D) : 10582$ înmulţiri
* $((AB)(CD)) : 54201$ înmulţiri
* $((A(BC))D) : 2856$ înmulţiri
* $(A((BC)D)) : 4055$ înmulţiri
* ...
 
Rezultatul optim se obţine pentru cea de a treia parantezare: $((A(BC))D)$.
 
h2. Indicaţii de rezolvare
 
Pentru cei care nu sunt familiarizaţi cu înmulţirea matricilor, recomand acest articol de pe 'wikipedia':http://en.wikipedia.org/wiki/Matrix_multiplication.
 
Înmulţirea matricilor este asociativă, motiv pentru care putem efectua aceste înmulţiri în mai multe moduri.
 
Înainte de a continua, să observăm că înmulţirea unei matrici cu $p x q$ elemente cu o matrice de $q x r$ elemente necesită $pqr$ înmulţiri scalare.
 
O soluţie directă de a determina ordinea optimă de efectuare a înmulţirilor matriciale este de a paranteza expresia în toate modurile posibile şi de a calcula de fiecare dată care este numărul de înmulţiri scalare necesare. Însă, numărul de moduri de a scrie un şir cu $n$ paranteze deschise şi $n$ paranteze închise, astfel încât să fie închise corect, este egal cu <tex> C(n) = \dfrac{1}{n+1} * \dbinom{2n}{n} </tex>. Şirul $(C(n))$ se numeşte 'şirul numerelor lui Catalan':http://www.ginfo.ro/revista/15_5/mate1.pdf. Aşadar, rezolvarea are o complexitate exponenţială.
 
Din fericire, principiul optimalităţii al metodei _programării dinamice_ se poate aplica la această problemă. Dacă cel mai bun mod de a înmulţi toate matricele presupune o tăietură între a $i$-a şi a $i + 1$ a matrice a produsului, atunci subprodusele $M{~1~}M{~2~}...M{~i~}$ şi $M{~i+1~}M{~i+2~}...M{~n~}$ trebuie calculate la rândul lor într-un mod optim.
 
Vom construi tabloul $m[1..n, 1..n]$, unde $m[i, j]$ este numărul minim de înmulţiri scalare necesare pentru a calcula partea $M{~i~}M{~i+1~}...M{~j~}$ a produsului iniţial. Soluţia problemei iniţiale va fi $m[1, n]$. Presupunem că tabloul $d[0..n]$ conţine dimensiunile matricilor, astfel încât matricea $M{~i~}$ este de dimensiuni $d[i-1] x d[i], 1 &le; i &le; n$. Construcţia tabloului se face diagonală cu diagonală:
 
* <tex> d = 0: m[i, i] = 0, 1 \le i \le n </tex>
* <tex> d = 1: m[i, i + 1] = d[i - 1] * d[i] * d[i + 1], 1 \le i \le n - 1 </tex>
* <tex> 1 < d < n: m[i, i + d] = Min\{m[i, k] + m[k + 1, i + d] + d[i - 1] * d[k] * d[i + d] : i \le k < i + d\}, 1 \le i \le n - d </tex>
 
Timpul de execuţie este de ordinul $O(N^3^)$, iar sursa demonstrativă se găseşte aici(?).
 
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:
 
* '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_

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