学步园

题目描述 Description

输入描述 Input Description

输出描述 Output Description

样例输入 Sample Input

样例输出 Sample Output

解题思路：

这道题显然是用动态规划，但是不同于背包问题，这是一种区间型动态规划类型。

我一开始就死在这一点上，后来才想通，在大神的指点下，慢慢把这道题做了出来，也发现了其中与背包问题的一些共同点。

先写出动态转移方程.

d(i，j）=min（d（i，k）+d（k+1，j)+sum(i，j））

表示合并区间[i,j]内所有石子所需要的最小代价。

发现没有，有了一个K。

这是为什么呢？

因为我们不知道这堆石子应该怎么分才能得到最小的代价，所以我们需要不断的设置断点，即取[i,k]后，取[k+ 1,j]，最后两者合并，注意不论怎么取，一定有代价sum[i,j]表示区间[i,j]的石子总代价。

代码如下：

#include <iostream>

using namespace std;

int tone[110];
int d[110][110];
int s[110];

int main(){
	int t;
	cin>>t;
	for(int i=1;i<=t;i++){
		cin>>tone[i];
		s[i]=s[i-1]+tone[i];
	}
	int min;
	for(int i=1;i<=t;i++){		
		for(int j=i+1;j<=t;j++){
			min=9999999;
			for(int k=i;k<j;k++){
				if(min>d[i][k]+d[k+1][j]+s[j]-s[i-1]){
					min=d[i][k]+d[k+1][j]+s[j]-s[i-1];
				}
			}
			d[i][j]=min;
		}
	}
	cout<<d[1][t];
} 
			

但这是错的！

为什么呢？

因为我们的循环的i是从1--t的，j是从i+1--t的，所以这是什么意思？

我们先枚举d[1][2···t],再枚举d[2][3···t]，但是d[1][t]又必须借助d[t-1][t],d[t-2][t],d[t-2][t-1]···这些结果。

毫无疑问，i按顺序写的话肯定错。反序的话就对了。

背包九讲第1讲就讲到了这个问题，有兴趣的话可以去看一下。

好了，附上正确代码：

#include <iostream>

using namespace std;

int tone[110];
int d[110][110];
int s[110];

int main(){
	int t;
	cin>>t;
	for(int i=1;i<=t;i++){			//从1开始，方便S[i]的取值计算
		cin>>tone[i];
		s[i]=s[i-1]+tone[i];		//优化s[i,j]
	}
	int min;
	for(int i=t-1;i>=1;i--){		  //这一顺序
		for(int j=i+1;j<=t;j++){
			min=9999999;
			for(int k=i;k<j;k++){		//注意K的取值从i到j-1，,否则越界，因为下面有k+1
				if(min>d[i][k]+d[k+1][j]+s[j]-s[i-1]){
					min=d[i][k]+d[k+1][j]+s[j]-s[i-1];	//取最小值
				}
			}
			d[i][j]=min;
		}
	}
	cout<<d[1][t];
}