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
#include <cstdio>
#include <algorithm>

typedef long long ll;

int n;

static inline int IK(int i, int k) {
    return i * n + k;
}

#define IJ IK

int main() {
    scanf("%d", &n);

    int *c = new int[n*n];
    int *lcost = new int[n*n];
    int *oldlcost = new int[n*n];
    ll *cost = new ll[n*n];

    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            scanf("%d", &c[IJ(i, j)]);
        }
    }

    for (int i = 0; i < n; ++i) {
        lcost[IK(i,i)] = c[IJ(i,i)];
        cost[IJ(i,i)] = c[IJ(i,i)];
    }

    /*
    for (int i = 0; i < n; ++i) {
        printf("lcost[%d,%d,%d] = %d\n", i, i, i, lcost[IK(i,i)]);
        printf("cost[%d,%d] = %lld\n", i, i, cost[IJ(i,i)]);
    }
    */

    for (int l = 2; l <= n; ++l) {
        std::swap(lcost, oldlcost);
        for (int i = 0; i + l <= n; ++i) {
            int j = i+l-1;
            int cij = c[IJ(i,j)];
            ll *curCost = &cost[IJ(i,j)];

            lcost[IK(i,i)] = std::min(oldlcost[IK(i,i)], cij);
            lcost[IK(i,j)] = std::min(oldlcost[IK(i+1,j)], cij);

            *curCost = std::min(lcost[IK(i,i)] + cost[IJ(i+1,j)], cost[IJ(i,j-1)] + lcost[IK(i,j)]);

            for (int k = i+1; k <= j-1; ++k) {
                lcost[IK(i,k)] = std::min(std::min(oldlcost[IK(i,k)], oldlcost[IK(i+1,k)]), cij);
                //printf("lcost[%d,%d,%d] = %d\n", i, k, j, lcost[IK(i,k)]);

                ll ikjCost = cost[IJ(i,k-1)] + lcost[IK(i,k)] + cost[IJ(k+1,j)];
                if (ikjCost < *curCost) {
                    *curCost = ikjCost;
                }
            }
            //printf("cost[%d,%d] = %lld\n", i, j, *curCost);
        }
    }

    printf("%lld\n", cost[IJ(0, n-1)]);
    
    return 0;
}