题目链接
题意：题目：有一个长l的木头，切成n+1段，切割的代价是当前段长度，求最小代价和。
解题报告：
对于区间DP，我们常常用dp[i][j]来表示，区间 [ i,j ] 的答案
一般的方程为 dp[i][j]=min/max{ dp[i][k],dp[k][j] } + w
在这道题中，我们用dp[i][j],来表示分割 i~j这根木棍的最小代价。
dp[i][j]=min(dp[i][k],dp[k][j])+len[j]-len[i]
#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
int a[55], d[55][55], len, n;
int main(){while( scanf("%d", &len)==1 && len ){scanf("%d", &n);for ( int i=1; i<=n; i++ ) scanf("%d", &a[i]);a[0]=0, a[n+1]=len;for ( int l=1; l-1<=n+1; l++ )for ( int i=0; i+l-1<=n+1; i++ ){int minv=(1<<31)-1;int j=i+l-1;d[i][j]=0;for ( int k=i+1; k<j; k++ ){int tmp=d[i][k]+d[k][j]+a[j]-a[i];if( minv>tmp ) minv=tmp;}if( minv!=(1<<31)-1 ) d[i][j]=minv;}printf("The minimum cutting is %d.\n", d[0][n+1] );}
}