本文主要是介绍Cutting Sticks UVA - 10003 (区间Dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
链接：点击打开链接
题目大意：有一根木棍长度为L，然后有N个切割点，将木棍切割成n+1段，当切割长度为Li时，那么需要Li的费用.例如有一个长度为10的木棍，切割点在2,4,7位置上，如果顺序切割的话：
1、首先长度为10，在2位置切割，那么sum+=10
2、再在剩下的长度为8的长度中切割4位置，那么sum+=8
3、再在剩下长度为6中切7位置，那么sum+=6==24
而如果按顺序4,2,7切割sum=20=10+4+6
问最小花费。
ps:紫书p278；这个题是最优矩阵链乘的变形体，也是个区间dp，因为刚学了矩阵链乘，所以看这个就比较简单了。
首先这里dp的是从0-L,而不是切割点的数量。先赋值最大，在区间i~j中找到一个切割点k，进行分割dfs(i,k)和dfs(k,j),记住边界不用切割，就算切割也是0，所以k从i+1~j-1;然后加上j-i的值。这里还要注意的是当i~j没有切割点时，不是返回的dp[i][j],而是返回的0，因为把dp初始化最大了，而不再切割也就意味着不再花费了，自然是0.
#include <iostream>
#include <bits/stdc++.h>
#define INF 0x3f3f3f3fusing namespace std;int dp[1005][1005];
int len,n;
int a[1005];
int dfs(int i,int j)
{int &ans=dp[i][j];if(ans<INF)return ans;if(i==j)ans=0;else{for(int k=i+1;k<j;k++){if(a[k]){int ret=dfs(i,k)+dfs(k,j)+j-i;if(ans>ret){ans=ret;}}}}if(ans==INF)ans=0;return ans;
}
int main()
{while(scanf("%d",&len),len){scanf("%d",&n);int x;memset(a,0,sizeof(a));for(int i=1;i<=n;i++){scanf("%d",&x);a[x]=1;}memset(dp,INF,sizeof(dp));dp[0][len]=dfs(0,len);printf("The minimum cutting is %d.\n",dp[0][len]);}return 0;
}
这篇关于Cutting Sticks UVA - 10003 (区间Dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
