Fişierul intrare/ieşire:triunghi3.in, triunghi3.outSursăONI 2010, clasa a 10-a
AutorMarius NicoliAdăugată demathboyDragos-Alin Rotaru mathboy
Timp execuţie pe test0.25 secLimită de memorie24096 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

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

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

Date de ieşire

În fişierul triunghi3.out se va scrie pe prima linie 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.

Exemplu

triunghi3.intriunghi3.out
4
10 8 6 4 3 12 3 1 6 5
235

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.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content