== include(page="template/taskheader" task_id="oracol") ==
Poveste şi cerinţă...
Gustavo, după ce a realizat că posedă abilitatea de a vedea în viitor, a decis că a venit momentul să treacă la următorul nivel şi să-şi valorifice capacităţile extrasenzoriale. Pentru a câştiga prestigiu şi a deveni mai cunoscut în rândurile magicienilor profesionişti, acesta a ales să debuteze la Olimpiada
Naţională de Informatică prin prezicerea datelor de intrare pentru anumite probleme propuse în concurs.
Primul client al lui Gustavo, Alfredo, ar dori să afle într-un mod inedit conţinutul unui fişier de intrare aferent unei probleme de concurs, în care sunt scrise elementele unui şir p de N numere întregi. Pentru a face lucrurile mai interesante, Gustavo îi percepe o taxă de $C(i,j)$ bănuţi pentru a-i divulga suma numerelor din şirul $p$ cu indici în intervalul $[i,j]$, anume $p{~i~} + p{~i+1~} + ... + p{~j~}$.
h2. Cerinţă
Dându-se valoarea lui $N$ şi toate valorile $C(i,j)$ cu $1 ≤ i ≤ j ≤ N$, determinaţi costul total minim pe care trebuie să-l plătească Alfredo pentru a afla toate elementele şirului $p$.
h2. Date de intrare
Fişierul de intrare $oracol.in$ ...
În fişierul $oracol.in$ se află pe prima linie numărul natural $N$. Pe următoarele $N$ linii se află taxele percepute de Gustavo astfel: pe linia $i+1$ se vor afla $N-i+1$ numere naturale separate prin câte un spaţiu, reprezentând în ordine costurile $C(i,i), C(i,i+1), ... , C(i,N)$.
h2. Date de ieşire
În fişierul de ieşire $oracol.out$ ...
În fişierul $oracol.out$ trebuie să se găsească un singur număr care reprezintă costul total minim pe care trebuie să-l plătească Alfredo pentru a afla şirul $p$.
h2. Restricţii
* $... ≤ ... ≤ ...$
* $1 ≤ N ≤ 1000$
* pentru orice $1 ≤ i ≤ j ≤ N$ se garantează $0 ≤ C(i,j) ≤ 1.000.000$.
* pentru teste în valoare de $48$ puncte $1 ≤ N ≤ 250$.
h2. Exemplu
table(example). |_. oracol.in |_. oracol.out |
| This is some
text written on
multiple lines.
| This is another
text written on
multiple lines.
| 3
4 5 1
6 3
2
| 6
|
h3. Explicaţie
...
Costul total minim este $6$ şi se obţine astfel:
Cu un cost de valoare $C(1,3)=1$ putem afla suma p{~1~} + p{~2~} + p{~3~}.
Cu un cost de valoare $C(3,3)=2$ putem afla valoarea lui p{~3~}.
Cu un cost de valoare $C(2,3)=3$ putem afla suma p{~2~} + p{~3~}.
Din acestea putem afla exact toate elementele şirului $p$.
== include(page="template/taskfooter" task_id="oracol") ==
