题目描述
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。
试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.
输入输出格式
输入格式：
数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.
输出格式：
输出共2行,第1行为最小得分,第2行为最大得分.
思路分析
一、贪心
贪心只能处理“任取两堆”，而不能处理“相邻两堆”。任取两堆的题目就是 合并果子。
二、划分阶段
本题是区间DP的模板题（然而对蒟蒻还是很难）
很容易想到用f[i][j]表示i~j的最大（小）得分。
三、状态转移
在i~j这一区间内，枚举下标k进行拆分。拆分区间是区间DP的重要思想之一。
合并i~k与k+1~j的区间，会加上i~j之间所有石子个数之和。
故我们得到状态转移方程为f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]+s[j]-s[i-1]) （最小值max改为min）
其中s为前缀和（不懂的自觉退役……自觉补习）。
四、环
dalao们可能会使用高级数据结构，但其实有一种更简单的方法：把原数组往后复制一遍。
以样例4 5 9 4为例，复制后得到：
4 5 9 4 4 5 9 4
i~j长度不能超过n
五、玄学40分
基础DP的代码比较简短，但麻烦的地方有很多，关键在于环。
for(int i=1;i<=n;i++) { for(int j=i+1;j<=2*n;j++) { if(j-i>=n) break; for(int k=i;k<j;k++) { ma[i][j]=max(ma[i][j],ma[i][k]+ma[k+1][j]+sum[j]-sum[i-1]); mi[i][j]=min(mi[i][j],mi[i][k]+mi[k+1][j]+sum[j]-sum[i-1]); } } }
这是之前的一份错误代码，它使用直接计算长度的方式来保证长度<=n。
但是这样的转移顺序会出现问题。如，外层循环i=1，第二层j=10，内层循环k=4时：
f[1][10]=max(f[1][10],f[1][4]+f[5][10]+s[10]-s[0])
可以发现f[5][10]还未转移，这也是玄学40分的原因。
解决方法倒是有不少，这里 借 鉴 了其他题解，用r=i+j-1来记录右边界，使r和i，j直接联系，完美避免了上述情况。
详情见代码。
七、代码
码风丑陋勿喷，没有优化勿喷。
另外，以此题的数据范围完全用不到四边形不等式这类的高档算法。
以后如果想起来，还会再来更新O(n2)算法（咕）
#include<iostream> #include<iomanip> #include<cstring> using namespace std; int n,a[205],mi[205][205],ma[205][205],sum[205],ansmax,ansmin,r; int main() { memset(mi,0x3f,sizeof(mi)); memset(ma,0,sizeof(ma)); //初始化 cin>>n; sum[0]=0; for(int i=1;i<=n;i++) { cin>>a[i]; a[i+n]=a[i]; //输入 } for(int i=1;i<2*n;i++) { sum[i]=sum[i-1]+a[i]; mi[i][i]=ma[i][i]=0; //维护前缀和，再次初始化数组 } for(int i=2;i<=n;i++) { for(int j=1;i+j-1<2*n;j++) { r=i+j-1; for(int k=j;k<r;k++) { ma[j][r]=max(ma[j][r],ma[j][k]+ma[k+1][r]+sum[r]-sum[j-1]); mi[j][r]=min(mi[j][r],mi[j][k]+mi[k+1][r]+sum[r]-sum[j-1]);//状态转移 } } } ansmin=0x7fffffff; ansmax=-1; for(int i=1;i<=n;i++) { ansmin=min(ansmin,mi[i][i+n-1]); ansmax=max(ansmax,ma[i][i+n-1]); //选择最大（小）值 } cout<<ansmin<<" "<<ansmax; return 0; }