== include(page="template/taskheader" task_id="triunghi3") ==
Se consideră o placă de dimensiune $n$, de forma unui triunghi echilateral, ale cărui laturi sunt denumite $A$, $B$ şi $C$ şi au lungimea egală cu $n$. Pe laturile $A$ şi $B$ sunt marcate câte $n - 1$ puncte care împart laturile în $n$ porţiuni egale. Din fiecare punct marcat de pe latura $A$ se trasează un segment paralel cu latura $B$, iar din fiecare punct marcat de pe latura $B$ se trasează un segment paralel cu latura $A$. Celălalt capăt al fiecărui segment trasat se află pe latura $C$. În felul acesta, placa triunghiulară conţine $n * (n + 1) / 2$ plăci elementare (care nu sunt traversate de niciun segment). Astfel, pe o placă triunghiulară de dimensiune $n = 4$, ca în figură, avem $6$ plăci elementare în formă de romb şi $4$ în formă de triunghi (cele cu o latură pe latura $C$ a plăcii triunghiulare).
!>problema/triunghi3?tringuh.jpg!
Se doreşte împărţirea triunghiului în plăci elementare cu cost total minim. Dacă $n = 1$ costul împărţirii este $0$. Pentru $n ≥ 2$ singura operaţie permisă este tăierea de la un capăt la altul de-a lungul unui segment de lungime maximă, obţinându-se un triunghi de dimensiune $n - 1$ şi o bandă. Banda va fi împărţită în plăci elementare prin tăieri de-a lungul segmentelor de lungime $1$ ce separă plăcile elementare care o compun. Triunghiul obţinut va fi împărţit mai departe în plăci elementare folosind în mod repetat operaţia descrisă mai sus. Costul total al împărţirii triunghiului de dimensiune $n$ în plăci elementare este egal cu costul tăierii de-a lungul segmentului de lungime maximă, plus costurile împărţirii benzii şi triunghiului de dimensiune $n - 1$ obţinute, în plăci elementare.
Pe fiecare placă elementară este scris un număr. Costul unei tăieturi (fie că are loc într-un triunghi sau într-o bandă) este egal cu suma valorilor din plăcile elementare care au o latură comună cu segmentul pe care se face tăietura, înmulţită cu lungimea segmentului. Pentru un triunghi de dimensiune $n ≥ 2$ există exact $2$ posibilităţi de a efectua o operaţie (corespunzătoare celor $2$ segmente de lungime maximă, unul paralel cu latura $A$, iar celălalt paralel cu latura $B$). O tăiere pe direcţia $NV - SE$ (paralelă cu latura $B$) în triunghiul din figură are costul $(8 + 10 + 3 + 6 + 6 + 12) * 3 = 135$. Costul împărţirii în plăci elementare a benzii obţinute este egal cu $(10 + 6) * 1 + (6 + 12) * 1 + (12 + 5) * 1 = 51$.
h2. Cerinţă
Să se determine costul total minim necesar împărţirii plăcii triunghiulare în plăci elementare.
Poveste şi cerinţă...
h2. Date de intrare
În fişierul $triunghi3.in$ pe prima linie se află un număr natural nenul $n$, reprezentând dimensiunea plăcii. Pe a doua linie apar separate prin câte un spaţiu $n * (n + 1) / 2$ numere naturale, reprezentând valorile plăcilor elementare în ordinea parcurgerii de sus în jos şi apoi de la stânga la dreapta, conform figurii de mai sus.
Fişierul de intrare $triunghi3.in$ ...
h2. Date de ieşire
În fişierul $triunghi3.out$ se va scrie pe prima linie costul total minim cerut.
În fişierul de ieşire $triunghi3.out$ ...
h2. Restricţii
* $1 ≤ n ≤ 1000$
* $0 ≤ numărul de pe o placă elementară ≤ 2 000 000 000$
* Se garantează că rezultatul se va încadra pe $32$ biţi.
* Pentru $50%$ din teste vom avea $n ≤ 400$.
* $... ≤ ... ≤ ...$
h2. Exemplu
table(example). |_. triunghi3.in |_. triunghi3.out |
| 4
10 8 6 4 3 12 3 1 6 5
| 235
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
|
h3. Explicaţie
Pentru a asigura costul total minim se poate realiza o tăietură pe direcţia $NE - SV$ de cost $3 * (10 + 6 + 8 + 3 + 4 + 1) = 96$ la care se adaugă costul tăierii benzii în plăci elementare $3 + 4 + 4 + 8 + 8 + 10 = 37$. Placa triunghiulară rămasă va fi tăiată pe direcţia $NE - SV$. Costul tăieturii este $2 * (3 + 6 + 6 + 12) = 54$, tăierea benzii în plăci elementare are costul $1 + 3 + 3 + 6 = 13$. Placa triunghiulară rămasă poate fi tăiată pe direcţia $NV - SE$. Costul tăieturii este $6 + 12 = 18$, tăierea benzii în plăci elementare are costul $12 + 5 = 17$, costul total minim este $235$.
...
== include(page="template/taskfooter" task_id="triunghi3") ==
