石子归并(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; }