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
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
#include <cstdio>

using namespace std;

int main()
{
    int n;

    scanf("%d", &n);

    long long **c = new long long*[2001];
    long long **d = new long long *[2001];
    for(int i = 0; i <= 2000; i++){
        c[i] = new long long[2001];
        d[i] = new long long[2001];
    }


    long long ctmp;
    long long ctmp1, ctmp2, ctmp3;


    for(int i = 1; i <= n; i++){
        for(int j = i; j <= n; j++){
            scanf("%lld", &ctmp);

            c[i][j] = ctmp;
        }
    }

    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= n; j++)
            d[i][j] = -1;
    }


    for(int i = 1; i <= n; i++)
        d[i][i] = c[i][i];

    // go by columns
    for(int j = 2; j <= n; j++){

        // iterate over j-th column
        for(int i = j-1; i >= 1; i--){

            // check i..k + k+1..j costs
//            for(int k = i; k < j; k++){
//                long long ctmp = c[i][k] + c[k+1][j];
//
//                if(c[i][j] >= ctmp) c[i][j] = ctmp;
//            }

            /// two parts
            /// [i]...[k][k+1].....[j]
            for(int k = i; k < j; k++){
                ctmp = d[i][k] + d[k+1][j];
                //printf("-- i= %d,k= %d,j= %d, val= %lld:\n", i, k, j, ctmp);
                if(d[i][j] > ctmp || d[i][j] == -1)
                    d[i][j] = ctmp;

            }

            /// three parts - [k] determined taking values from c
            /// [i]...[k-1][k][k+1]...[j]

            for(int k = i; k <= j; k++){
                for(int l = i; l <= k; l++){

                    for(int r = j; r >= k; r--){

                    //printf("--i= %d, j= %d, k= %d, l= %d, r= %d\n", i, j, k, l, r);

                        if(k-1 >= i){
                            ctmp1 = d[i][k-1];
                        }
                        else ctmp1 = 0;

                        if(k+1 <= j){
                            ctmp2 = d[k+1][j];
                        }
                        else ctmp2 = 0;

                        ctmp3 = c[l][r];

                        ctmp = ctmp1 + ctmp2 + ctmp3;

                        if(ctmp < d[i][j] || d[i][j] == -1){
                            d[i][j] = ctmp;
                        }
                    }

                }
            }

        }
    }

    printf("%lld", d[1][n]);

}