http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944
区间dp，对于每段区间，他们的最优值都是由几段更小区间的最优值得到，是分治思想的一种应用，将一个区间问题不断划分为更小的区间直至一个元素组成的区间，枚举他们的组合，求合并后的最优值。
在左右两端加上两个端点，区间dp即可。
1 #include <cstdio> 2 #include <cstring> 3 #include <algorithm> 4 #define maxn 10000 5 using namespace std; 6 const int inf=1<<29; 7 8 int l,n; 9 int c[maxn]; 10 int dp[1001][1001]; 11 12 13 int main() 14 { 15 while(scanf("%d",&l)!=EOF) 16 { 17 if(l==0) break; 18 scanf("%d",&n); 19 for(int i=1; i<=n; i++) 20 { 21 scanf("%d",&c[i]); 22 } 23 c[0]=0; c[n+1]=l; 24 memset(dp,0,sizeof(dp)); 25 for(int i=2; i<=n+1; i++) 26 { 27 for(int j=0; j+i<=n+1; j++) 28 { 29 int min1=inf; 30 for(int k=j+1; k<j+i; k++) 31 { 32 if(min1>dp[j][k]+dp[k][j+i]) 33 { 34 min1=dp[j][k]+dp[k][j+i]; 35 } 36 } 37 dp[j][j+i]=min1+c[j+i]-c[j]; 38 } 39 } 40 printf("The minimum cutting is %d. ",dp[0][n+1]); 41 } 42 return 0; 43 }