== 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).
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.
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$.
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ţă
