Problem oracol


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

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.

Date de intrare

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

Date de ieșire

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

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.

Exemplu

oracol.in

3
4 5 1
6 3
2

oracol.out

6

Explicații

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.

General info

ID: 10

Upload: liviu

Input: oracol.in/oracol.out

Memory limit: 128MB/8MB

Time limit: 0.3s

Author: Oncescu Costin Andrei

Source: ONI 2019 XI-XII: Ziua 1, Problema 2

Submissions

Special Submissions