学步园

9-8还没做完，感觉有点困难。回头再做

这道题很好的训练了最优矩阵连乘。记忆化搜索TLE了，递推则很顺畅。

递推的顺序：不能按照以前的方法递推，因为求某一个区间的解的时候要用到它子区间的解，如果按照以前的顺序递推，则子区间的解此时还没有求出来。所以先把长度为1的子区间的解求出来，这样就能求长度为2的子区间的解，然后就能求3、4...直到n+1

Run Time: 0.135s

#define UVa  "LT9-9.10003.cpp"		//Cutting Sticks
char fileIn[30] = UVa, fileOut[30] = UVa;

#include<cstring>
#include<cstdio>
#include<algorithm>

using namespace std;

//Global Variables. Reset upon Each Case!
const int maxn = 50 + 10, maxl = 1000 + 10;
int l, n;
int c[maxn];
int d[maxl][maxl];
/////

int main() {
    while(scanf("%d", &l) && l) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i ++) scanf("%d", &c[i]);
        c[0] = 0;
        c[n+1] = l;

        for(int len = 1; len <= n+1; len ++) {
            for(int i = 0; i+len <= n+1; i ++) {
                int j = i + len;
                if(len == 1)
                    d[i][j] = 0;
                else {
                    d[i][j] = d[i][i+1] + d[i+1][j];
                    for(int k = i + 2; k < j; k ++)
                        d[i][j] = min(d[i][j], d[i][k]+d[k][j]);
                    d[i][j] += c[j] - c[i];
                }
            }
        }
        printf("The minimum cutting is %d.\n", d[0][n+1]);
    }

    return 0;
}

//Memoization, TLE:
//int dp(int i, int j) {
//    if(d[i][j] != -1) return d[i][j];
//    if(i >= j-1) d[i][j] = 0;
//    else {
//        int w = c[j] - c[i];
//        d[i][j] = dp(i,i+1) + dp(i+1,j) + w;
//        for(int k = i+2; k < j; k ++)
//            d[i][j] = min(d[i][j], dp(i,k)+dp(k,j)+w);
//    }
//    return d[i][j];
//}