1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#include <iostream>
using namespace std;

int tab[2005][2005];
int tab2[2005][2005];

int main(){
  ios_base::sync_with_stdio(0);
  int n;
  cin >> n;
  for(int i=0; i<n; i++)
    for(int j=0; j<n-i; j++) cin >> tab[i+1][i+j+1];
  for(int i=0; i<n; i++) tab2[i+1][i+1]=tab[i+1][i+1];
  for(int i=1; i<=n; i++) // dlugosc przedzialu
    for(int j=1; j<=n-i; j++){ // poczatek przedzialu
      int pocz=j;
      int kon=j+i;
      long long min=1000000000000000005;
      for(int k=pocz; k<kon; k++){
//        cout << "pocz " << pocz << " kon " << kon << ": pocz " << pocz << " k " << k << " tab2 " << tab2[pocz][k] << " k+1 " << k+1 << " kon " << kon << " tab2 " << tab2[k+1][kon] << " suma  " << tab2[pocz][k]+tab2[k+1][kon] << endl;
        if(min>tab2[pocz][k]+tab2[k+1][kon]) min=tab2[pocz][k]+tab2[k+1][kon];
        }
      for(int k=pocz; k<kon-1; k++){
      long long min2=1000000000005;
      for(int l=k+1; l<kon; l++) {
  //      cout << "pocz " << pocz << " kon " << l << endl;
        if(tab2[pocz][l]<min2) min2=tab2[pocz][l];
        if(tab[pocz][l]<min2) min2=tab[pocz][l];
        }
      for(int l=pocz+1; l<=k+1; l++)
        for(int p=k+1; p<=kon; p++) {
//          cout << "pocz " << l << " kon " << p << endl;
          if(tab2[l][p]<min2) min2=tab2[l][p];
          if(tab[l][p]<min2) min2=tab[l][p];
        }
      if(tab[pocz][kon]<min2) min2=tab[pocz][kon];

//	        cout << pocz << " kon " << kon << ": pocz " << pocz << " k " << k <<  " tab2 " << tab2[pocz][k] << " k+2 " << k+2 << " kon " << kon << " tab2 " << tab2[k+2][kon] << " min2 " << min2 << " suma  " << tab2[pocz][k]+tab2[k+2][kon]+min2 << endl;   
                if(min>tab2[pocz][k]+tab2[k+2][kon]+min2)
        min=tab2[pocz][k]+tab2[k+2][kon]+min2;
        }
  //    cout << "pocz " << pocz << " kon " << kon << ": pocz " << pocz << " kon " << kon << " tab " << tab[pocz][kon] << " pocz " << pocz << " kon-1 " << kon-1 << " tab2 " << tab2[pocz][kon-1] << " suma " << tab[pocz][kon]+tab2[pocz][kon-1] << endl;
      if(min>tab[pocz][kon]+tab2[pocz][kon-1]) min=tab[pocz][kon]+tab2[pocz][kon-1];
//cout << "pocz " << pocz << " kon " << kon << ": pocz " << pocz << " kon " << kon << " tab " << tab[pocz][kon] << " pocz+1 " << pocz+1 << " kon " << kon << " tab2 " << tab2[pocz+1][kon] << " suma " << tab[pocz][kon]+tab2[pocz+1][kon] << endl;
      if(min>tab[pocz][kon]+tab2[pocz+1][kon]) min=tab[pocz][kon]+tab2[pocz+1][kon]; 
        tab2[pocz][kon]=min;
    }
/*    for(int i=0; i<n; i++){
      for(int j=0; j<i; j++) cout << "  ";
      for(int j=0; j<n-i; j++) cout << tab2[i+1][j+i+1] << " ";
      cout << endl;
      }*/
  cout << tab2[1][n] << endl;
  return 0;
}