石子归并（区间型dp） 代码日志

石子归并（merge）

【问题描述】

在一个操场按次序从左到右摆放着n堆石子(n≤100)，现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分，求最小的得分总和。

【输入格式】

第一行为石子堆数n；

第二行为每堆的石子数，每两个数之间用一个空格分隔。

【输出格式】

最小的得分总和。

【输入样例】

6

3 4 6 5 4 2

【输出样例】

61

样例说明：

3 4 6 5 4 2

7 6 5 4 2

13 5 4 2

13 5 6

13 11

24

7+13+6+11+24=61

【代码日志】

（然鹅我觉得我的决策比样例解释更好）

#include<bits/stdc++.h>
using namespace std;
int n,s[105],sum[105];
int dp[105][105];
int opt[105][105];
//dp[i][j]将第i颗到第k颗石头合并的最大分值 
//sum[i]将前i颗石头合并的数值 
//推方程
//dp[i][j]=max(dp[i][k]+dp[k+1][j])(i<=k<=j-1)
int main(){
	freopen("merge.in","r",stdin);
	freopen("merge.out","w",stdout);
	cin>>n;
	sum[0]=0;
	for(int i=1;i<=n;i++){
		cin>>s[i];
		sum[i]=sum[i-1]+s[i];
		dp[i][i]=0;
	}
	for(int k=2;k<=n;k++){
	//k指将原来分别为i堆的石子合并为一堆 
		for(int i=1;i<=n-k+1;i++){
			dp[i][i+k-1]=0;
			int ssum = sum[i+k-1] - sum[i-1];
			for(int j=i;j<=i+k-2;j++){
				//cout<<"\t("<<i<<".."<<j<<")["<<dp[i][j]<<"] + ("<<j+1<<".."<<i+k-1<<")["<<dp[j+1][i+k-1]<<"] = ("<<i<<".."<<i+k-1<<")["<<dp[i][i+k-1]<<"]"<<endl;
				if(dp[i][i+k-1]<dp[i][j]+dp[j+1][i+k-1]+ssum){
					dp[i][i+k-1]=dp[i][j]+dp[j+1][i+k-1]+ssum;
					opt[i][i+k-1]=j;
				}
			}
//下一行输出决策，若想验证请去掉注释符号
			//cout<<"\t\tBEST (k ="<<k<<") : ("<<i<<".."<<opt[i][i+k-1]<<")["<<dp[i][opt[i][i+k-1]]<<"] + ("<<opt[i][i+k-1]+1<<".."<<i+k-1<<")["<<dp[opt[i][i+k-1]+1][i+k-1]<<"] = ("<<i<<".."<<i+k-1<<")["<<dp[i][i+k-1]<<"]"<<endl;
		}
	}
	cout<<dp[1][n]<<endl;
	return 0;
}