题目链接：
题意： L长的木棍，给n个切割点，切成n+1部分，每次切割的时候的费用等于切割时的长度。求最少费用。
这个题目和最优矩阵链乘一样，DP方向既不是顺序，也不是逆序，而是，较大部分状态取决于小部分状态的决策。
d(i,j) 切 i 和 j 的最少费用，那么方程就是 d(i,j) = min(d(i,k)+d(k,j)+a[j]-a[i]);(a[j]-a[i])就是切 i~j的费用。
顺便说一下最优矩阵链乘， n*m 的矩阵 和 m*p 的矩阵，相乘的次数是 n*m*p，矩阵链乘满足结合律，最优矩阵链乘的状态转移方程就是 f(i,j) = min(f(i,k)+f(k+1,j)+pi-1*pk*pj);
切木棍问题也可以用哈夫曼数来做，之前的一篇博客中有写。
#includeusing namespace std;#define maxn 55#define INF 0x3f3f3f3fint a[maxn],vis[maxn][maxn],d[maxn][maxn];int L,n;int dp(int i,int j){ if(i>=j-1) return 0; if(vis[i][j]) return d[i][j]; vis[i][j] = 1; int & ans = d[i][j]; for(int k=1; k<=j-1; k++) ans = min(ans,dp(i,k)+dp(k,j)+a[j]-a[i]); return ans;}int main(){ while(scanf("%d",&L),L) { scanf("%d",&n); for(int i=1; i<=n; i++) scanf("%d",&a[i]); a[0] = 0; a[n+1] = L; memset(d,INF,sizeof(d)); memset(vis,0,sizeof(vis)); int ans = dp(0,n+1); printf("The minimum cutting is %d.\n",ans); } return 0;}
