Nu aveti permisiuni pentru a descarca fisierul grader_test8.ok

Diferente pentru problema/triunghi3 intre reviziile #5 si #6

Nu exista diferente intre titluri.

Diferente intre continut:

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.
!>problema/triunghi3?tringuh.jpg!
 
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$.
p=. !problema/triunghi3?tringuh.jpg!
 
h2. Cerinţă

Nu exista diferente intre securitate.

Topicul de forum nu a fost schimbat.