[关闭]
@feiyangyang 2022-07-11T07:56:00.000000Z 字数 14548 阅读 334

合并石子（区间DP）

题解

重点推荐：

dp的for，状态转移看不懂的来看看我这一篇题解，准保刷新思路！
我是一个dp的蒟蒻，就是怎么也理解不了dp

我换了一种思路：不会for但是可以递归呀，把一个大问题分解成若干个小问题再逐一解决
解释：
我定义函数doit（ x , y ）返回值是将区间[ x , y ]的石子合并后得到的最小值

再处理一个前缀和方便查询某个区间的和

因为石子是一圈一圈的，所以我们要把它展开

对于以上的详细解释，可以看其他题解，本题解主要提供一个新的思路！！

记忆化：
因为不停的递归会超时，于是我们可以加一个记忆化数组jy[205]（ji-yi记忆,音译而来）这样程序就可以跑得飞快了
到这听不懂没关系，代码里面有超详细解释（^.^）

  1. # include <iostream>
  2. # include <cstdio>
  3. # include <cmath>
  4. # include <algorithm>
  5. # include <queue>
  6. # include <stack>
  7. using namespace std;
  8. int read();
  9. int n;//这个还要解释，那还是去再读一边题吧
  10. int a[205];//存a[i]这堆石子的数量
  11. int add[205];//前缀和，方便查询
  12. int jy[205][205];//记忆最小的合并值
  13. int jy2[205][205];//记忆最大的合并值
  14. int sum1,sum2;
  15. int doit(int x,int y);//声明递归最小的合并值
  16. int doit2(int x,int y);//声明递归最大的合并值
  17. int main()//---------------------主函数----------------------
  18. {
  19.     n=read();
  20.     for(int i=1;i<=n;i++)
  21.     {
  22.         a[i]=read();
  23.         add[i]+=a[i]+add[i-1];//前缀和
  24.     }
  25.     for(int i=n+1;i<=n*2;i++)//展开
  26.     {
  27.         a[i]=a[i-n];//a[数组]重复来一波
  28.         add[i]+=a[i]+add[i-1];//add继续加前缀和
  29.     }
  30.     int ans1=9999999,ans2=0;//用来更新区间最值的变量
  31.     for(int i=1;i<n;i++)
  32.     {
  33.             //枚举区间，更新区间最值
  34.         ans1=min(ans1,doit(i,i+n-1));
  35.         ans2=max(ans2,doit2(i,i+n-1));
  37.     }
  38.     printf("%d\n%d",ans1,ans2);//输出更新的值
  39.     return 0;
  40. }
  42. int doit(int x,int y)//求最小合并值doit------------------------------
  43. {//重点了，注意看！！！！！！！！！！！！！
  44.     if(x==y)return 0;//跑到点上去了，返回0，因为要求的是区间和，和单个点权值无关
  45.     if(jy[x][y])return jy[x][y];//记忆化，如果之前求过这个
  46.                     //区间的值，直接返回，快得起飞
  47.     int ans=9999999;//定义一个ans用来更新最小合并值
  48.     int tes=add[y]-add[x-1];//这个是区间[x,y]的和
  49.     //add[ ]是前缀和
  50.     for(int k=x;k<y;k++)
  51.     {
  52.     //枚举k，更新区间[x,y]的最小合并值
  53.         ans=min(ans,doit(x,k)+doit(k+1,y)+tes);  
  54.     }
  55.     jy[x][y]=ans;//记忆这个值
  56.     return ans;返回求到的这个区间最小合并值
  57. }
  59. int doit2(int x,int y)//求最大合并值doit2----------------------------
  60. {
  61.     //这里和doit差不多，只是min变成了max
  62.     //我就不重复解释了
  63.     if(x==y)return 0;
  64.     if(jy2[x][y])return jy2[x][y];
  65.     int ans=0;
  66.     int tes=add[y]-add[x-1];
  67.     for(int k=x;k<y;k++)
  68.     {
  69.         ans=max(ans,tes+doit2(x,k)+doit2(k+1,y));
  70.     }
  71.     jy2[x][y]=ans;
  72.     return ans;
  73. }
  75. //读入优化
  76. int read()
  77. {
  78.     int ans=0,flag=1;
  79.     char ch=getchar();
  80.     while(ch>'9'||ch<'0')
  81.     {
  82.         if(ch=='-')
  83.         {
  84.             flag=-1;
  85.             ch=getchar();
  86.             break;
  87.         }
  88.         ch=getchar();
  89.     }
  90.     while(ch>='0'&&ch<='9')
  91.     {
  92.         ans=ans*10+ch-'0';
  93.         ch=getchar();
  94.     }
  95.     return ans*flag;
  96. }

Corrine
更新时间：2017-12-16 20:51:06
在 Ta 的博客查看

这是一道区间dp十分经典的模板题，让我们揣测一下，前辈们是如何得到这个状态转移方程的。

首先，要计算合并的最大值、最小值，既然是动态规划，我们需要洞悉其中一些关联且确定的状态。

以下以最大值为例。

既然是最大值，那么求得的结果是否满足每一区间都是该区间所能达得到的的最大值？

显然是这样的。反证法：倘若有一个区间不是，那么换做该区间取得最大值的方案，最终结果将比原得分大。显然必定满足任意区间得分一定是该区间内的最大值。

这样我们可以定义状态f[i][j]，表示i到j合并后的最大得分。其中1<=i<=j<=N。

既然这样，我们就需要将这一圈石子分割。很显然，我们需要枚举一个k，来作为这一圈石子的分割线。

这样我们就能得到状态转移方程：

f[i][j] = max(f[i][k] + f[k+1][j] + d(i,j));其中，1<=i<=<=k

d(i,j)表示从i到j石子个数的和。

那么如何编写更快的递推来解决这个问题？

在考虑如何递推时，通常考虑如下几个方面：

是否能覆盖全部状态？

求解后面状态时是否保证前面状态已经确定？

是否修改了已经确定的状态？

也就是说，在考虑递推顺序时，务必参考动态规划的适应对象多具有的性质，具体参考《算法导论》相关或百度百科或wiki。

既然之前说过我们需要枚举k来划分i和j，那么如果通过枚举i和j进行状态转移，很显然某些k值时并不能保证已经确定过所需状态。

如，i=1 to 10,j=1 to 10,k=1 to 9.当i=1,j=5,k=3时，显然状态f[k+1][j]没有结果。

那么，我们是不是应该考虑枚举k？

但这样i和j就难以确定了。

我们不难得到一个两全的方法：枚举j-i，并在j-i中枚举k。这样，就能保证地推的正确。

上代码[cpp]

  1. include<iostream>  
  2. include<cstdio>  
  3. include<cmath>  
  4. using namespace std;   
  5. int n,minl,maxl,f1[300][300],f2[300][300],num[300];  
  6. int s[300];  
  7. inline int d(int i,int j){return s[j]-s[i-1];}  
  8. //转移方程：f[i][j] = max(f[i][k]+f[k+1][j]+d[i][j];
  9. int main()  
  10. {   
  11.     scanf("%d",&n);  
  12.     for(int i=1;i<=n+n;i++)  //好吧，终于有时间看看评论区，看来大家对这里异议蛮多的，这里统一解释一下，因为是一个环，所以需要开到两倍再枚举分界线，最后肯定是最大的 
  13.     {  
  14.         scanf("%d",&num[i]);  
  15.         num[i+n]=num[i];  
  16.         s[i]=s[i-1]+num[i];  
  17.     }  
  18.     for(int p=1;p<n;p++)  
  19.     {  
  20.         for(int i=1,j=i+p;(j<n+n) && (i<n+n);i++,j=i+p)  
  21.         {  
  22.             f2[i][j]=999999999;  
  23.             for(int k=i;k<j;k++)  
  24.             {  
  25.                 f1[i][j] = max(f1[i][j], f1[i][k]+f1[k+1][j]+d(i,j));   
  26.                 f2[i][j] = min(f2[i][j], f2[i][k]+f2[k+1][j]+d(i,j));  
  27.             }  
  28.         }  
  29.     }  
  30.     minl=999999999;  
  31.     for(int i=1;i<=n;i++)  
  32.     {  
  33.         maxl=max(maxl,f1[i][i+n-1]);  
  34.         minl=min(minl,f2[i][i+n-1]);  
  35.     }  
  36.     printf("%d\n%d",minl,maxl);  
  37.     return 0;  
  38. }

Hurricane、
更新时间：2017-12-21 17:21:36
在 Ta 的博客查看
如果对于任意的a1≤a2< b1≤b2，有m[a1,b1]+m[a2,b2]≤m[a1,b2]+m[a2,b1]，那么m[i,j]满足四边形不等式。

所以这是一个求(xuan)骗(xue)的东西。

定理

对方程

且s(i,j)表示m(i,j)取得最优值时对应的下标，有：

区间包含的单调性：如果对于i≤i'< j≤j'，有w(i',j)≤w(i,j')，那么说明w具有区间包含的单调性。
区间包含的单调性

四边形不等式：如果对于i≤i'< j≤j'，有w(i,j)+w(i',j')≤w(i',j)+w(i,j')，我们称函数w满足四边形不等式。
四边形不等式

蓝线长和≤红线长和

定理一：如果上述的w函数同时满足区间包含单调性和四边形不等式性质，那么函数m也满足四边形不等式性质。

定理二：假如m(i,j)满足四边形不等式，那么s(i,j)单调，即s(i,j)≤s(i,j+1)≤s(i+1,j+1)。

然后k的范围就从 [ i , j ] 变成了[ s(i,j-1) , s(i+1,j) ]，像这样：

表

m[1,3]取s[1,2]和s[2,3]，

m[2,5]取s[ 2,4]=3，s[3,5]=3，相当于直接取3。

（然后记s[2,5]=3）

少了一重循环！！！

完美解释了OBST问题！！！

（其实就是套定理）

题目

NOI 1995 石子合并

(洛谷 P1880)

n<=100……如果n<=1000呢？

100的O(n^3)O(n
3
)还能过，1000的就得O(n^2)O(n
2
)了。

环形的……也不惧……

但最大值不单调，不能用四边形不等式

不过最大值可以两个端点的最大者取得。

最大值不单调

详解

题解 by myself

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. int a[2005],sum[2005];
  5. int fmi[2005][2005],fma[2005][2005],
  6.     smi[2005][2005];
  8. int main(){
  9.     int n;
  10.     scanf("%d",&n);
  11.     for(int i=1;i<=n;i++){
  12.         scanf("%d",&a[i]);
  13.         a[i+n]=a[i];
  14.         sum[i]=sum[i-1]+a[i];
  15.         smi[i][i]=i;
  16.         }
  17.     for(int i=1+n;i<=(n<<1);i++){
  18.         sum[i]=sum[i-1]+a[i];
  19.         smi[i][i]=i;
  20.         }
  21.     for(int i=(n<<1)-1;i;i--)
  22.         for(int j=i+1;j<=(n<<1);j++){
  23.             int jc=0,tmp=0x3f3f3f3f;
  24.             fma[i][j]=max(fma[i][j-1],fma[i+1][j])+sum[j]-sum[i-1];
  25.             /*注意这句，
  26.               求最大值不能用四边形不等式，
  27.               因为最大值不满足单调性，
  28.               但最大值有一个性质，
  29.               即总是在两个端点的最大者中取到。
  30.             */
  31.             for(int k=smi[i][j-1];k<=smi[i+1][j];k++){
  32.                 int tt=fmi[i][k]+fmi[k+1][j]+(sum[j]-sum[i-1]);
  33.                 if(tt<tmp){
  34.                     tmp=tt;
  35.                     jc=k;
  36.                     }
  37.                 }
  38.             smi[i][j]=jc;
  39.             fmi[i][j]=tmp;
  40.             }
  41.     int ama=0,ami=0x3f3f3f3f;
  42.     for(int i=1;i<=n;i++){
  43.         ama=max(ama,fma[i][i+n-1]);
  44.         ami=min(ami,fmi[i][i+n-1]);
  45.         }
  46.     printf("%d\n%d",ami,ama);
  47.     ```
  48.     return 0;
  49.     }
  50.     /*
  51. FFF团 更新时间：2017-09-14 15:20:13 在 Ta 的博客查看 本题如果要写动态规划的话，不仅要考虑推的顺序还要考虑边界与初始化的问题；
  53. 这时候不如记忆化搜索，因为搜索时可以避免顺序问题边界也非常容易设计；
  55. 但不管是记忆化还是动态规划都要考虑环的问题，这时不如直接将环拆为2*n的链来考虑，因为2*n的链已经足够考虑到所有情况了；

代码来一发

  1. include<cstdio>
  2. include<iostream>
  3. include<cstring>
  4. using namespace std;
  5. const int INF=0x7fffffff;
  6. int n,m,ans1,ans2;
  7. int A[205],f1[205][205],f2[205][205];
  8. int dfs1(int L,int R){                //求出最小得分 
  9.     if(f1[L][R])return f1[L][R];    //已保存的状态不必搜索 
  10.     if(L==R)    return f1[L][R]=0;    //L==R时返回0 
  11.     int res=INF;                    //初始值赋为最大值以求最小值 
  12.     for(int k=L;k<R;k++)            //枚举K搜索 
  13.         res=min(res,dfs1(L,k)+dfs1(k+1,R)+A[R]-A[L-1]);
  14.     return f1[L][R]=res;            //记录状态 
  15. }
  16. int dfs2(int L,int R){                //求出最大得分 
  17.     if(f2[L][R])return f2[L][R];
  18.     if(L==R)    return f2[L][R]=0;    //若初始值为0可省略该句 
  19.     int res=0;                        //初始值设为0 
  20.     for(int k=L;k<R;k++)
  21.         res=max(res,dfs2(L,k)+dfs2(k+1,R)+A[R]-A[L-1]);
  22.     return f2[L][R]=res;
  23. }
  24. int main(){
  25.     std::ios::sync_with_stdio(false);//取消cin与stdin同步,加速读入 
  26.     cin>>n;
  27.     for(int i=1;i<=n;i++){
  28.         cin>>A[i];
  29.         A[i+n]=A[i];                //因为是环所以保存为长度为2n的链以保证不会漏解 
  30.     }
  31.     for(int i=1;i<=2*n;i++)            //求出前缀和 
  32.         A[i]+=A[i-1];
  33.     dfs1(1,2*n);dfs2(1,2*n);        //搜索出1-2n的最大得分与最小得分 
  34.     ans1=INF;    ans2=0;
  35.     for(int i=1;i<=n;i++){
  36.         ans1=min(f1[i][n+i-1],ans1);//选出答案 
  37.         ans2=max(f2[i][n+i-1],ans2);
  38.     }
  39.     cout<<ans1<<"\n"<<ans2;
  40.     return 0;
  41. }

逆流之时
更新时间：2019-02-04 16:57:25
在 Ta 的博客查看
这篇题目已经有四边形不等式的题解了，我就做一点补充吧。
1.为什么长度为n的环可以看做长度为2n的链？
因为n堆石子会合并n-1次，就像并查集一样，最后总会刚好有两端是没有连接的，所以计算最大值可以这样算，然后从中选取长度为n且分数最大的一段链。
2.为什么最大值从可以两个端点的最大者取得？
首先可以把最后一步看成两堆石子合并，倒数第二部看成三堆石子中的两堆合并，再与第三堆合并。
那三堆中哪两堆合并呢？
(用w[i]表示第i堆重量)
前两堆:w1=2w[1]+2w[2]+w[3]w1=2w[1]+2w[2]+w[3]
后两堆:w2=w[1]+2w[2]+2w[3]w2=w[1]+2w[2]+2w[3]（自行推导)
所以应该将1号和3号中较大的一堆与第2堆合并，也就是把一堆合并得尽可能大，所以就有

dp2[i][j]=max(dp2[i+1][j],dp2[i][j-1])+cnt[j]-cnt[i-1];
再贴上完整代码

  1. #include<iostream>
  2. #include<cstdio>
  3. using namespace std;
  4. int cnt[210],s[210][210],dp[210][210],n,temp,te,dp2[210][210],maxn,minn;
  5. int main()
  6. {
  7.     scanf("%d",&n);
  8.     for(int i=1;i<=n;i++)scanf("%d",&cnt[i]),cnt[i]+=cnt[i-1],s[i][i]=i,s[i+n][i+n]=i+n;
  9.     for(int i=1;i<=n;i++)cnt[i+n]=cnt[i]+cnt[n];
  10.     for(int i=n*2;i>=1;i--)
  11.         for(int j=i+1;j<=n*2;j++)//参考第1点
  12.         {
  13.             temp=0x7fffffff;
  14.             dp2[i][j]=max(dp2[i+1][j],dp2[i][j-1])+cnt[ j]-cnt[i-1]; //参考第2点
  15.             for(int k=s[i][j-1];k<=s[i+1][j];k++)
  16.             {
  17.                 if(temp>dp[i][k]+dp[k+1][j]+cnt[j]-cnt[i-1])
  18.                 {
  19.                     temp=dp[i][k]+dp[k+1][j]+cnt[j]-cnt[i-1];
  20.                     te=k;
  21.                 }
  22.             }
  23.             dp[i][j]=temp;
  24.             s[i][j]=te;
  25.         }
  26.     minn=0x7fffffff;
  27.     for(int i=1;i<=n;i++)
  28.     {
  29.         minn=min(minn,dp[i][i+n-1]);
  30.         maxn=max(maxn,dp2[i][i+n-1]);
  31.     }
  32.     printf("%d\n%d",minn,maxn);
  33.     return 0;
  34. }

由上面的推导可以得到：w1<=w2w1<=w2时，w[1]<=w[3]w[1]<=w[3]。
其实这就是GarsiaWachs算法的思想。石子合并题解里没有大佬讲这个算法。貌似在《The Art of Computer Programming》上有。虽然我也没用看过
这个算法可以将石子合并问题优化到O(nlogn)O(nlogn)的规模，目前百度上关于这个算法的博客不多，绝大部分都以石子合并为例题，关于这个算法的其他用途我还在探索中。
这个算法的具体思想是：设一个序列是w[1..n]w[1..n]（在这题里面就是当前n堆石子的质量），每次寻找最小的一个满足w[k-1]<=w[k+1]w[k−1]<=w[k+1]的kk。
那么我们就把w[k]w[k]与w[k-1]w[k−1]合并，之后找最大的一个满足w[j]>w[k]+w[k-1]w[j]>w[k]+w[k−1]的j(j 由于可以把从w[j+1]w[j+1]到w[i-2]w[i−2]的石子看成一个整体w[mid]w[mid],现在考虑三堆石子的情况：w[j],w[mid],temp(w[i]+w[i-1])w[j],w[mid],temp(w[i]+w[i−1]), 因为temp 本来这个算法的原复杂度是O(n^2)O(n
2
)，加上了平衡树优化的时间复杂度是O(nlogn)O(nlogn)。
然而GarsiaWachs算法的常数十分小。FHQ在POJ上发了讲解这个算法的帖：http://poj.org/showmessage?message_id=146323 ，他就用这个算法的朴素O(n^2)过了POJ的n=50000的数据。

题外话：
关于主流算法讲解书对动态规划、四边形不等式优化动态规划和GarsiaWachs算法的讲解与重视程度：
目前就我买的几本书中，只有很少的几本提到了四边形不等式。
信息学奥赛一本通：极少的讲解，大量例题与讲解内容抄袭，看过就知道。背包九讲不知道是不是抄的，不过例题有很多都是抄的，而且换到书里的题目背景还严重影响阅读体验。
紫书（《算法竞赛入门经典》）：讲dp主要目的是锻炼思维，提到的动态规划优化方法极少。
蓝书（《算法竞赛入门经典训练指南》）：没有dp专题。第一章略提到了四边形不等式。（本来我买这本书就是因为紫书第11章提到了蓝书讲过四边形不等式，结果买来一看，也没有详细的证明，四边形不等式的证明基本都被省略了）
算法竞赛进阶指南：动态规划讲了15章，是我看的所有竞赛书里最详细的一本，四边形不等式有详细的证明，不过GarsiaWachs算法只是提到了一下。（毕竟是专门讲dp的章节，而GarsiaWachs算法并不属于dp）
我列举这些信息的目的，是为了让大家意识到，动态规划的知识已经有很多，尽管有很多地方（而且包括很多讲解详细的书籍）都没有详细提及，但dp确实是OI很重要的一部分。洛谷的石子合并题解有40篇左右，但很多人的题解都停留在O(n^3)O(n
3
)的算法上，少数人提到了四边形不等式，但全部没有四边形不等式的详细证明，而且也没有讲解GarsiaWachs算法的题解。所有希望大家能在学习OI的时候，一直保持着对新知识的求知精神。

跪下叫哥
更新时间：2019-01-29 15:36:57
在 Ta 的博客查看
石子合并
分析
4 5 9 4
首先当然一条链来做， 那么最后一次合并（所有的石子合并成一堆）的时候的，得到是什么？

4+5+9+4
最后一次合并一定是两堆石子合并，关键是这两堆石子有可能的是：

第1种可能性:(4),(5,9,4) 4是一堆石子,(5,9,4)合并的一堆石子 第2种可能性:(4,5),(9,4) 第3种可能性:(4,5,9),(4)

所以,我们更加抽象一点来思考,设f(i,j)表示第i堆石子到第j堆石子合并成一堆石子的最大得分,sum(i,j)表示第i到第j的和:

f(i,j) = max{f(i,k)+f(k+1,j)} +sum(i,j) i<=k

k表示把i和j从中间分开,边界f[i][i] = 0

所以一条链的石子合并就OK了,关键环形的怎么做

最简单的想法:从环每一个点拆成多条链,分别求每条链的最大值,然后从这些最大值中找一个最大的,就是答案,例如样例数据可以写成

4 5 9 4 5 9 4 4 9 4 4 5 4 4 5 9

可以写成4条链.

但是这样拆环,你会发现,你重复的计算了一些数据

4 [5 9 4] [5 9 4] 4 9 4 4 5 4 4 5 9

你重复计算了(4,5,9) 合并的一堆石子的最大值.

应该这样拆环成链

4 5 9 4 4 5 9

包含了上面的所有的链,你要求的是

f(1,4) ==>4 5 9 4 f(2,5) ==>5 9 4 4 f(3,6) ==>9 4 4 5 f(4,7) ==>4 4 5 9

这样做的好处是:不会重复计算

因为: 你先算:f(1,2),f(2,3),f(3,4),f(4,5),f(5,6),f(6,7) 长度为2的 再算:f(1,3),f(2,4),f(3,5),f(4,6),f(5,7) 长度为3 最后算:f(1,4),f(2,5),f(3,6),f(4,7) 长度为4 边界:f(i,i) = 0

状态转移方程：

f(i,j) = max{f(i,k) +f(k+1,j) } +sum(i,j)
边界:

f(i,i) = 0
推导过程 f(1,2) = f(1,1) +f(2,2)+ sum(1,2)

f(1,3) = { 1: f(1,1)+f(2,3) 2: f(1,2)+f(3,3) }

4 5 9 4 5 9 4 4 9 4 4 5 4 4 5 9

4 5 9 4 4 5 9

代码

  1. #include <cstdio>
  2. #include <cstring>
  4. int n;
  5. int a[200];
  8. int f[200][200] = {0}; //不用初始化边界了
  9. int fx[200][200] = {0}; //不用初始化边界了,存最小值
  10. int pre[200] = {0};
  11. int ans_max = -1;
  12. int ans_min = 0x7f7f7f7f;
  15. int max(int a,int b){
  16.     if( a >b ) return a;
  17.     return b;
  18. }
  20. int min(int a,int b){
  21.     if( a <b ) return a;
  22.     return b;
  23. }
  25. int sum(int i,int j){
  26.     return pre[j] - pre[i-1];
  27. }
  29. int main(){
  30.     int i,j,k;
  31.     scanf("%d",&n);
  32.     for(i=1;i<=n;i++){
  33.         scanf("%d",&a[i]);
  34.         a[n+i] = a[i];
  35.     }
  37.     int len = (n<<1)-1;
  38.     for(i=1;i<=len;i++){
  39.         pre[i] = pre[i-1] +a[i];
  40.     }
  42.     memset(fx,0x7f,sizeof(fx));
  43.     for(i=0;i<=200;i++) fx[i][i] = 0;
  47.     for(i=2;i<=n;i++){ // 合并几堆石子
  48.         for(j=1;j<=len-i+1;j++){
  49.             for(k=j;k<j+i-1;k++){
  50.              int m =  f[j][k] + f[k+1][j+i-1];
  52.              int xiao = fx[j][k] +fx[k+1][j+i-1];
  54.              if( f[j][j+i-1] < m) //求 max
  55.                  f[j][j+i-1] = m;
  57.              if( fx[j][j+i-1] > xiao) //求 max
  58.                  fx[j][j+i-1] = xiao;
  59.             }
  60.             f[j][j+i-1] += sum(j,j+i-1);
  61.             fx[j][j+i-1] += sum(j,j+i-1);
  62.         }
  63.     }
  65.     for(i=1;i<=n;i++){
  66.         if( ans_max < f[i][i+n-1])
  67.             ans_max = f[i][i+n-1];
  69.         if( ans_min > fx[i][i+n-1])
  70.             ans_min = fx[i][i+n-1];
  71.     }
  72.     printf("%d\n",ans_min);
  73.     printf("%d",ans_max); return 0;}

Kevin_Wa
更新时间：2019-01-04 06:29:50
在 Ta 的博客查看
本题初看以为可以使用贪心法解决问题，但是事实上因为有必须相邻两堆才能合并这个条件在，用贪心法就无法保证每次都能取到所有堆中石子数最多的两堆。例如下面这个例子：

6
3 4 6 5 4 2
如果使用贪心法求最小得分，应该是如下的合并步骤：

第一次合并 3 4 6 5 4 2    2,3合并得分是５
第二次合并 5 4 6 5 4      5,4合并得分是9
第三次合并 9 6 5 4        5,4合并得分是9
第四次合并 9 6 9          9,6合并得分是15
第五次合并 15 9           15,9合并得分是24
总得分＝5＋9＋9＋15＋24＝62

但是如果采用如下合并方法，却可以得到比上面得分更少的方法：
第一次合并 3 4 6 5 4 2 3,4合并得分是7
第二次合并 7 6 5 4 2 7,6合并得分是13
第三次合并 13 5 4 2 4,2合并得分是6
第四次合并 13 5 6 5,6合并得分是11
第五次合并 13 11 13,11合并得分是24
总得分＝7＋13＋6＋11＋24＝61
由此我们知道本题是不可以使用贪心法求解的，上例中第五次合并石子数分别为1313和1111的相邻两堆。 这两堆石头分别由最初 的第11，22，33堆（石头数分别为33，44，66）和第44，55，66堆（石头数分别为55，44，22）经44次合并后形成的。于是问题又归结为如何使得这两个子序列的N-2N−2次合并的得分总和最优。为了实现这一目标，我们将第11个序列又一分为二：第11、22堆构成子序列11，第33堆为子序列22。第一次合并子序列１１中的两堆，得分77；第二次再将之与子序列22的一堆合并，得分1313。显然对于第11个子序列来说，这样的合并方案是最优的。同样，我们将第22个子序列也一分为二；第44堆为子序列11，第55，66堆构成子序列22。第三次合 并子序列22中的22堆，得分22；第四次再将之与子序列11中的一堆合并，得分1313。显然对于第二个子序列来说，这样的合并方案也是最优的。由此得出一个结论──66堆石子经过这样的55次合并后，得分的总和最小。

动态规划思路：
阶段i：石子的每一次合并过程，先两两合并，再三三合并，...最后N堆合并

状态s：每一阶段中各个不同合并方法的石子合并总得分。

决策：把当前阶段的合并方法细分成前一阶段已计算出的方法，选择其中的最优方案

具体来说我们应该定义一个数组s[i,j]用来表示合并方法，i表示从编号为i的石头开始合并，j表示从i开始数j堆进行合并，s[i,j]为合并的最优得分。

对于上面的例子来说，初始阶段就是s[1,1],s[2,1],s[3,1],s[4,1],s[5,1],s[6,1]，因为一开始还没有合并，所以这些值应该全部为0。

第二阶段：两两合并过程如下，其中sum(i,j)表示从i开始数j个数的和
s[1,2]=s[1,1]+s[2,1]+sum(1,2)
s[2,2]=s[2,1]+s[3,1]+sum(2,2)
s[3,2]=s[3,1]+s[4,1]+sum(3,2)
s[4,2]=s[4,1]+s[5,1]+sum(4,2)
s[5,2]=s[5,1]+s[6,1]+sum(5,2)
s[6,2]=s[6,1]+s[1,1]+sum(6,2)

第三阶段：三三合并可以拆成两两合并，拆分方法有两种，前两个为一组或后两个为一组
s[1,3]=s[1,2]+s[3,1]+sum(1,3)或s[1,3]=s[1,1]+s[2,2]+sum(1,3)，取其最优
s[2,3]=s[2,2]+s[4,1]+sum(2,3)或s[1,3]=s[2,1]+s[3,2]+sum(2,3)，取其最优
.
.
.
第四阶段：四四合并的拆分方法用三种，同理求出三种分法的得分，取其最优即可。以后第五阶段、第六阶段依次类推，最后在第六阶段中找出最优答案即可。

由此得到算法框架如下：
For j←2 to n do {枚举阶段，从两两合并开始计算}
For i←1 to n do {计算当前阶段的n种不同状态的值}
For k←1 to j-1 do {枚举不同的分段方法}
begin
If i+k>n then t←(i+k) mod n else t←i+k {最后一个连第一个的情况处理}
s[i,j]←最优{s[i,k]+s[t,j-k]+sum[1,3]} {sum[i,j]表示从i开始数j个数的和}
end;

Anubis
更新时间：2018-10-25 20:29:51
在 Ta 的博客查看
题目解析：

第一次做这种题型的大佬们应该不会把它当成贪心来做吧？？？反正小蒟蒻我是做错了啦！！！

后面有分析了几个手推数据，发现！！！ 这是一题动规，还是一题区间动规！！！

让我们先看看样例： 这是最小值的求法，看起来好像和贪心很像勒！！！但其实只是样例数据给出的假象罢了！！！

很多的大佬和蒟蒻做题时用了贪心结果只有30分！！！

首先如何解决上图环的问题呢？？？ 　 当然很简单啦，我们把它存成一条链：即把T存成2*T

如：2 3 4 6 5 4 2 3 4 6 5 4 这样每次枚举i到i+N-1就可以了是吧是不是很简单啊(^▽^ ) (i<=N)

上文我们说到这是一题动规，那么我们来分析一下：

1.根据题意可知每次都是两堆石子合并成一堆，并且这两堆石子是相邻的！！

那么这两堆石子又是由另外的石子合并的，那么我们可以认为i到j堆石子是由F[i][k]和F[k+1][j]合成的。那么F[i][k]也是根据上面的规则求得到！！！

2.那么合成的分数如何表示的呢？？？( -'`-)

已知每个点的分数都是确定的，那么无论前面的数据如何合并的分数一定是由前面sum[j]-sum[i-1]的值，sum[i]=sum[i-1]+T[i];， 　　 因此得到F[i][j]=max(F[i][k]+[k+1][j]+sum[j]-sum[i-1],F[i][j]); 　　 　 　至此这题大水题已经解决了剩下的只是要考虑合并几次的问题而已

因为第一次至少两堆合并，那么就有了L (L=2；L<=N;++L)j=i+L-1;

最后就是求一下答案枚举一遍就行了！！

下面正解代码：1

  1. using namespace std;
  2. const int MAXN=0xfffff,MINN=0;
  3. inline int read()//快读
  4. {
  5.    int x=0,w=0;
  6.     char ch=0;
  7.     while(!isdigit(ch))
  8.     {
  9.         w|=ch=='-',ch=getchar();
  10.     }
  11.     while(isdigit(ch))
  12.     {
  13.         x=(x<<1)+(x<<3)+(ch^48),ch=getchar();
  14.     }
  15.     return w?-x:x;
  16. }
  17. int T[210],F1[210][210],F2[210][210],sum[210];//T为输入的石子堆，F1为第一问的答案求解，F2为第二问的答案求解，sum为求前ｉ堆石子的合总值
  18. int main(void)
  19. {
  20.     int N=read();
  21.     for(int i=1; i<=N; ++i) T[i]=read(),T[i+N]=T[i];／／变环为链
  22.     for(int i=1; i<=2*N; ++i) sum[i]=sum[i-1]+T[i],F1[i][i]=0,F2[i][i]=0;//注意要把Ｆ［ｉ］［ｉ］＝０
  23.     for(int L=2; L<=N; ++L)
  24.     {
  25.         for(int i=1; i<=2*N-L+1; ++i)
  26.         {
  27.             int j=i+L-1;
  28.             F1[i][j]=MAXN,F2[i][j]=MINN;//初始化
  29.             for(int k=i; k<j; ++k)
  30.             {
  31.                 F1[i][j]=min(F1[i][k]+F1[k+1][j],F1[i][j]);//寻找最小值
  32.                 F2[i][j]=max(F2[i][k]+F2[k+1][j],F2[i][j]);//寻找最大值
  33.             }
  34.             F1[i][j]+=(sum[j]-sum[i-1]);//加上此次合并值
  35.             F2[i][j]+=(sum[j]-sum[i-1]);
  36.         }
  37.     }
  38.     int ANS1=MAXN,ANS2=MINN;
  39.     for(int i=1; i<=N; ++i)
  40.     {
  41.         ANS1=min(ANS1,F1[i][i+N-1]);//求解答案１
  42.         ANS2=max(ANS2,F2[i][i+N-1]);//求解答案２
  43.     }
  44.     printf("%d\n%d",ANS1,ANS2);//输出
  45.     return 0;}

xhsr_120
更新时间：2019-08-01 11:47:44
在 Ta 的博客查看
经典的区间DP
题目传送门

看到这道题我第一眼想到DP和贪心。 但必须要相邻的才能合并，所以果断选择DP；

  1. 读入
    这道题就是一个断环为链的操作，如果输入的为x1,x2,x3,…… x2,那么我们把xn+1赋值为x1，xn+2赋值为x2，……,xn+n赋值为xn;

for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i+n]=a[i];
}
那我们就会发现从x1到x 2*n就是一个环，我们可以理解成环上的DP

状态转移 把当前阶段的合并方法细分成前一阶段已计算出的方法，选择其中的最优方案
for(int i=1;i<=n;i++)
{
for(int l=1;l+i<=2*n;l++)
{
int r=l+i-1;
for(int mid=l;mid {
Max[l][r]=max(Max[l][mid]+Max[mid+1][r]+w[r]-w[l-1],Max[l][r]);
Min[l][r]=min(Min[l][mid]+Min[mid+1][r]+w[r]-w[l-1],Min[l][r]);

                }
         } 
}

优化
为了防止自己合并自己，我们可以将这种可能赋值为0，即使自己合并自己，也不会有结果；

for(int i=1;i<=2*n;i++)
{
w[i]=w[i-1]+a[i];
}
输出
这题是求最大值和最小值。我们可以过一遍Max和Min两个数组，打擂求出答案

int ans=0,ans1=0x7f7f7f7f;//最大值和最小值
for(int i=1;i<=n;i++)
{
ans=max(ans,Max[i][i+n-1]);
ans1=min(ans1,Min[i][i+n-1]);
}
cout<

完整代码
求dalao指点

GEM_077
更新时间：2017-08-15 15:56:18
在 Ta 的博客查看

贪心明显不行：每次找两个合并代价最小的堆合并？那我们来举一个例子？

8 4 6 3 5

贪心的结果为62，而最优解为60。

那么如何动规呢？

其实这是一道典型的环状线性dp（注：∈为包含）

我们假设f[l,r]表示从第l堆合并到第r堆的最优方案，对于每一个f[l,r]，我们枚举每一个k∈[l+1..r]来比较，通过f[l,k-1]和f[k,r]合并到f[l,r]所产生的答案从而得出f[l,r]的最优解，最后的答案即为###max/min(f[i,i+n-1]) (i∈[1..n])

不要忘了处理环 ###

添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注