【动态规划】22.石子合并

【动态规划】22.石子合并

问题描述：在一个圆形操场的四周摆放着n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。

试设计一个算法。

1. 选择一种合并石子的方案，使得做 n-1 次合并得分总和最大。
2. 选择一种合并石子的方案，使得做 n−1 次合并得分总和最小。

算法设计：对于给定n堆石子,计算合并成一堆的最小得分和最大得分。

数据输入：

第一行是正整数n(1<=n<=200),表示有n堆石子。

第2行有n个数，分别表示每堆石子的个数。

输出格式
输出共两行：

第一行为合并得分总和最小值，

第二行为合并得分总和最大值。

输入：

4
4 5 9 4

输出：

43
54

代码：

问题不具有局部最优代替整体最优，不能用贪心法。

但是可以分为子问题，选择不同的堆进行合并。

动态规划——状态转移方程——找分割点

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;int n;//n堆石子
const int N=410;
int amax[N][N];
int amin[N][N];
int sum[N];//前缀和 
int a[N];
const int MAX=0x3f3f3f3f; int main()
{cin>>n;memset(amin,MAX,sizeof(amin));memset(amax,0,sizeof(amax));for(int i=1;i<=n;i++){cin>>a[i];a[i+n]=a[i];//扩展数组，将环形转化为线性 }sum[0]=0;//这里 for(int i=1;i<=2*n;i++){	amin[i][i]=0;amax[i][i]=0;sum[i]= sum[i-1]+a[i];//前缀和 } /*处理环的问题，将环剪成链，分别求max和min amin[l][r] =  min(amin[l][r] ,amin[l][k]+amin[k+1][r]+sum[r]-sum[l-1])amin[l][r] l到r 石子合并得到的最小分数 = min（l到r的最小得分，l到k k+1到r sum[r]-sum[l-1]最后两堆石子合并为最终结构时所得分数 ） sum[r]前r个石子总和 amax[l][r] =  max(amax[l][r] , amax[l][k] +amax[k+1][r]+sum[r]-sum[l-1])*/for(int len=2;len<=n;len++)//阶段：枚举区间长度，len记录相邻合并的石子数 {for(int ll=1;ll+len-1<=2*n;ll++)//状态：枚举区间起点 {int r=ll+len-1;//区间终点for(int k=ll;k<r;k++)//决策：枚举分割点 {amin[ll][r]=min(amin[ll][r] ,amin[ll][k]+amin[k+1][r]+sum[r]-sum[ll-1]);amax[ll][r]=max(amax[ll][r] ,amax[ll][k]+amax[k+1][r]+sum[r]-sum[ll-1]);//cout<<"amax["<<ll<<"]["<<r<<"]:"<<amax[ll][r]<<endl; } }}int resmin=MAX,resmax=0;for(int i=1;i<=n;i++)//枚举区间起点 {resmin=min(resmin,amin[i][i+n-1]);//从 i 到 i+n-1 的最小得分 resmax=max(resmax,amax[i][i+n-1]);//cout<<resmax<<" ";}cout<<resmin<<endl<<resmax<<endl; return 0;
}