uva10003 Cutting Sticks

题目大意： 

有一根长度为l的木棍，木棍上面有m个切割点，每一次切割都要付出当前木棍长度的代价，问怎样切割有最小代价

/*
    类似石子归并的区间dp 
*/
#include<iostream>
#include<cstdio>
#include<cstring>
#define INF 99999999
using namespace std;
int dp[1010][1010],n,sum[60],l;
int main(){
    //freopen("Cola.txt","r",stdin);
    while(1){
        scanf("%d",&l);
        if(l==0)return 0;
        memset(dp,0,sizeof(dp));
        scanf("%d",&n);
        for(int i=1;i<=n;i++)scanf("%d",&sum[i]);
        sum[n+1]=l;
        for(int len=1;len<=n+1;len++){
            for(int i=0;i<=n+1;i++){
                int j=i+len;
                if(j>n+1)break;
                int mn=INF;
                for(int k=i+1;k<j;k++){
                    mn=min(mn,dp[i][k]+dp[k][j]+sum[j]-sum[i]);
                }
                if(mn<INF)dp[i][j]=mn;
            }
        }
        printf("The minimum cutting is %d.
",dp[0][n+1]);
    }
}