【题目描述】
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。 试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
【输入格式】
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
【输出格式】
输出共2行,第1行为最小得分,第2行为最大得分
【样例输入】
4 4 4 5 9
【样例输出】
43
54
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define h 4001
using namespace std;
/*
第一种考虑思维：
f[i][j]意思是从堆i到堆j合并花费的最小值。
合并石子是一个合并类的动态规划问题，f[i][j]合并费用最小，则看是否存在k使得f[i][k]+f[k+1][j]+sum[i][j]更小
(其中sum[i][j]表示石子i堆到j堆得数量之和，它表示把已合并的[i][k]与[k+1][j]两堆再合并的花费)
这样的处理方法，就类似于最短路径问题了，欲求[i][j]之间的最短路，看是否能存在中间连接点k使得[i][k]+[k][j]路程更短的问题
动归方程: f[i][j]=min(f[i][j],(f[i][k]+f[k+1][j])+sum[i][j])，i=<k<j(f[k][k]=0)
第二种开率思维：
第一种方案是枚举[i...j]之间的k，找出能使得f[i][j]合并费用的最小的k使得f[i][j]=f[i][k]+f[k+1][j]+sum[i][j]取到最小值
换一个角度思考，递推的角度出发，首先肯定是计算序列中合并石子堆数少的时候的值，然后再一步步去计算合并更多堆石子的花费
例如：3 1 2 5 4这五堆石子，选择连续的两堆合并时的花费f[i][i+1]=w[i]+w[i+1]即可，但是合并连续的三堆的时候就麻烦了一些
假如是合并：3 1 2这三堆的时候，不得不去考虑是先合并1 2再合并3，还是先合并3 1再合并2.(f[2][3]和f[1][2]之前都计算出最优值)
事实上当合并3 1 2 5前面四堆石子的时候，最小花费考虑也只要考虑先合并3 1 2再合并5，还是先合并1 2 5再合并3的问题。
于是动归方程：f[i][j]=min(f[i+1][j],f[i][j-1])+sum[i][j]
细心的朋友可能发现第二种方案不就是第一种方案的特殊情况吗？只分析了当k=i和k=j-1的情况(f[i][i]=0),但是这种处理方法
符合动态规划的无后序性和最优性原则，得到的结果和方案一是一致的，事实上第一种方案使得结果最优的k值也肯定不只有一个的。
环形DP问题，处理技巧
理论上线性序列按照上面的思路去处理合并的问题，必定会得到最优解的。但是面对环形的问题又会产生额外的许多麻烦。
因为1 2 3 1这样的序列最优的办法是先合并1 1，然后再合并2，最后去合并3。但是这是一个线性的序列前面的f[i][j]我们处理的
时候都是认为i<=j的。总不能去求f[4][1]的值吧。
对于这个棘手的环，我们最好的办法是将其打开，使其变成一个序列。将1 2 3 1展开变成1 2 3 1 1 2 3 1 这样的线性序列即可，
那么这个序列中连续4个堆合并最优的花费值，即为所求。弄明白以后问题就很简单了。
*/
int f_max[h][h]={0}; //存储合并最大花费
int f_min[h][h]; //存储合并最小花费
int n,sum[h][h]; //存储sum[i][j],i->j连续石子堆的数量和
int a[h]={0}; //a[i],储存石子a[i]堆石子的数量
void work_min();
void work_max();
int main()
{
freopen("stone3.in","r",stdin);
freopen("stone3.out","w",stdout);
cin>>n;
for(int i=1; i<=n; i++)
{
cin>>a[i];
a[i+n]=a[i]; //变成2N长度的线性序列，像破碎的项链一样复制一遍。。
}
memset(sum,0,sizeof(sum));
for(int i=1;i<=2*n;i++) //计算sum[i][j],注意sum[i][i]这样的情况不需要情况，没有发生合并，花费值为0
{
int tot=a[i];
for(int j=i+1;j<=2*n;j++)
{
tot+=a[j];
sum[i][j]=tot;
}
}
work_min();
work_max();
return 0;
}
void work_min() //方案一求解合并石子最小花费
{
for(int d=2;d<=n;d++) //连续合并石子的堆数
for(int i=1;i<=2*n-d+1;i++) //起点
{
int j=i+d-1; //终点
f_min[i][j]=0x7f7f7f7f; //计算合并石子花费最小的时候，c初始化f_min[][]为最大的值
for(int k=i;k<j;k++) //在[i,j]中间插入k
{
f_min[i][j]=min(f_min[i][j],f_min[i][k]+f_min[k+1][j]+sum[i][j]);
}
}
//上面的动态规划(递推过程)，已经找出展开环后的2N长度序列中，所有的连续N堆石子合并时的最小花费，
//接下来只要判断2N序列中的哪一段连续N堆石子合并的花费值最小，即为目标的最优解。
int tot1=0x7f7f7f7f; //寻找最小值
for(int i=1;i<=n;i++) ////2N长度的堆中，求解所有长度为N的连续序列合并最小值
{
if(f_min[i][i+n-1]<tot1) tot1=f_min[i][i+n-1];
}
cout<<tot1<<endl;
return ;
}
void work_max() //方案2的思路
{
for(int d=2;d<=n;d++) //d表示参与合并的石子堆数
{
for(int i=1;i<=2*n-d+1;i++) //合并的起点，注意计算合并花费最大的时候，f_max[i][j]=0;
{
int j=i+d-1; //合并的终点
f_max[i][j]=max(f_max[i+1][j],f_max[i][j-1]); //方案2的核心思想，考虑先处理[i+1][j]还是[i][j-1]的情况比较
f_max[i][j]+=sum[i][j]; //不管怎样，最后合并起来的时候花费都为sum[i][j]
}
}
//上面的动态规划(递推过程)，已经找出展开环后的2N长度序列中，所有的连续N堆石子合并时的最优花费，
//接下来只要判断序列中哪一段连续N堆石子合并的花费值最大，即为目标的最优解。
int tot2=0; //2N长度的堆中，求解所有长度为N的连续序列合并最大值
for(int i=1;i<=n;i++) //寻找最大值
{
if(f_max[i][i+n-1]>tot2) tot2=f_max[i][i+n-1];
}
cout<<tot2<<endl;
return ;
}