UVA - 10003 Cutting Sticks 区间DP

题目大意：给出一根木棒长l，上面有k个点，要求从这些点切割，每次切割的代价是当前要切割的木棒的长度，求最小的代价

解题思路：区间DP：

区间动态规划问题一般都是考虑，对于每段区间，他们的最优值都是由几段更小区间的最优值得到，是分治思想的一种应用，将一个区间问题不断划分为更小的区间直至一个元素组成的区间，枚举他们的组合 ，求合并后的最优值。
设F[i,j]（1<=i<=j<=n）表示区间[i,j]内的数字相加的最小代价
最小区间F[i,i]=0（一个数字无法合并，∴代价为0）

每次用变量k（i<=k<=j-1）将区间分为[i,k]和[k+1,j]两段

For p:=1 to n do // p是区间长度，作为阶段。

for i:=1 to n do // i是穷举的区间的起点
begin
j:=i+p-1; // j是 区间的终点，这样所有的区间就穷举完毕
if j>n then break; // 这个if很关键。

for k:= i to j-1 do // 状态转移，去推出 f[i,j]
f[i , j]= max{f[ i,k]+ f[k+1,j]+ w[i,j] } 
end; 
这个结构必须记好，这是区间动态规划的代码结构。

转换公式为：f[i][j] = f[i][k] + f[k][j] + cut[j]- cut[i],f[i][j]表示从长度i到j的所要付出的最小代价，cut［j］-cut［i］表示如果从当前区间切割的话，这段代价是必然要付出的,这题记得加上0和l，因为这两点题目没有给出，得自己添加

#include<cstdio>
#include<cstring>
const int maxn = 50 + 5;
int l,n;
int DP[maxn][maxn],cut[maxn];
void dp() {

	memset(DP,0,sizeof(DP));
	for(int i = 1; i <= n + 1; i++) {//段大小
		for(int j = 0; j <= n + 1 - i; j++) {//起点
			int k = j + i;//终点
			int min = 0x3f3f3f3f;
			int temp;
			for(int l = j + 1; l < k; l++)  {
				temp = DP[j][l] + DP[l][k] + cut[k] - cut[j];			
				if(temp < min) {
					min = temp;
				}
			}
			if(min != 0x3f3f3f3f)
				DP[j][k] = min;
		}
	}
 
	printf("The minimum cutting is %d.\n",DP[0][n+1]);
}

int main() {
	while(scanf("%d", &l) != EOF && l) {
		scanf("%d", &n);
		for(int i = 1; i <= n; i++)
			scanf("%d", &cut[i]);	
		cut[0] = 0;
		cut[n+1] = l;	
		dp();
	}
	return 0;
}

更短的代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define INF 0x3f3f3f3f
const int maxn = 50 + 5;
int c[maxn];
int dp[maxn][maxn];

int main() {
	int len,num;
	while(scanf("%d",&len) != EOF && len) {
		scanf("%d",&num);
		for(int i = 1; i <= num; i++)
			scanf("%d",&c[i]);
		c[0] = 0;
		c[num+1] = len;
		memset(dp,0,sizeof(dp));
		for(int i = 2; i <= num + 1; i++)
			for(int j = 0; j + i <= num + 1; j++) {
				int k = i + j;	
				dp[j][k] = INF;
					for(int l = j ; l <= k; l++)	
						dp[j][k] = min(dp[j][k],dp[j][l] + dp[l][k] + c[k] - c[j]);
			}
		printf("The minimum cutting is %d.\n",dp[0][num+1]);
	}
	return 0;
}