#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; }
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; } |