d(i,j)表示将第i个切割点到第j个切割点分成i-j段所花费的最小代价，d(i,j)=min(d(i,k)+d(k,j)+a(i)-a(j)),为什么可以这样设置，因为我们考虑（i,j）的最小切割代价的时候，只有第一刀的代价是可以直接知道的，以此可以作为状态间转移的“跳板”。
#include<iostream> #include<cstdlib> #include<cstring> #include<cstdio> using namespace std; int l,n,cutt[55],d[55][55]; int main() { // freopen("1.txt","w",stdout); while(cin>>l&&l) { memset(d,0x3f3f3f,sizeof(d)); scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&cutt[i]); cutt[n+1]=l; for(int i=0;i<=n-1;i++) d[i][i+2]=cutt[i+2]-cutt[i]; for(int i=0;i<=n;i++) d[i][i+1]=0; for(int i=3;i<=n+1;i++)//枚举切割数 for(int j=0;j<=n+1-i;j++) for(int k=j+1;k<=j+i-1;k++) d[j][j+i]=min(d[j][j+i],d[j][k]+d[k][j+i]+cutt[j+i]-cutt[j]); cout<<"The minimum cutting is "<<d[0][n+1]<<'.'<<endl; } }