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).
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.
Cerinţă
Să se determine costul total minim necesar împărţirii plăcii triunghiulare în plăci elementare.
Date de intrare
În fişierul triunghi2.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.
Date de ieşire
Fişierul triunghi2.out va conţine o singură linie pe care se va scrie costul total minim cerut.
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.
Exemple
triunghi2.in
triunghi2.out
Explicaţii
4
10 8 6 4 3 12 3 1 6 5
235
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.
