题解 P1880 【[NOI1995]石子合并】

· · 题解

这篇题目已经有四边形不等式的题解了，我就做一点补充吧。
1.为什么长度为n的环可以看做长度为2n的链？
因为n堆石子会合并n-1次，就像并查集一样，最后总会刚好有两端是没有连接的，所以计算最大值可以这样算，然后从中选取长度为n且分数最大的一段链。
2.为什么最大值从可以两个端点的最大者取得？
首先可以把最后一步看成两堆石子合并，倒数第二部看成三堆石子中的两堆合并，再与第三堆合并。
那三堆中哪两堆合并呢？
(用w[i]表示第i堆重量)
前两堆:w1=2w[1]+2w[2]+w[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];

再贴上完整代码

#include<iostream>
#include<cstdio>
using namespace std;
int cnt[210],s[210][210],dp[210][210],n,temp,te,dp2[210][210],maxn,minn;
int main()
{
    scanf("%d",&n);
    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;
    for(int i=1;i<=n;i++)cnt[i+n]=cnt[i]+cnt[n];
    for(int i=n*2;i>=1;i--)
        for(int j=i+1;j<=n*2;j++)//参考第1点
        {
            temp=0x7fffffff;
            dp2[i][j]=max(dp2[i+1][j],dp2[i][j-1])+cnt[j]-cnt[i-1]; //参考第2点
            for(int k=s[i][j-1];k<=s[i+1][j];k++)
            {
                if(temp>dp[i][k]+dp[k+1][j]+cnt[j]-cnt[i-1])
                {
                    temp=dp[i][k]+dp[k+1][j]+cnt[j]-cnt[i-1];
                    te=k;
                }
            }
            dp[i][j]=temp;
            s[i][j]=te;
        }
    minn=0x7fffffff;
    for(int i=1;i<=n;i++)
    {
        minn=min(minn,dp[i][i+n-1]);
        maxn=max(maxn,dp2[i][i+n-1]);
    }
    printf("%d\n%d",minn,maxn);
    return 0;
}

由上面的推导可以得到：w1<=w2时，w[1]<=w[3]。
其实这就是GarsiaWachs算法的思想。石子合并题解里没有大佬讲这个算法。貌似在《The Art of Computer Programming》上有。虽然我也没用看过
这个算法可以将石子合并问题优化到O(nlogn)的规模，目前百度上关于这个算法的博客不多，绝大部分都以石子合并为例题，关于这个算法的其他用途我还在探索中。
这个算法的具体思想是：设一个序列是w[1..n]（在这题里面就是当前n堆石子的质量），每次寻找最小的一个满足w[k-1]<=w[k+1]的k。
那么我们就把w[k]与w[k-1]合并，之后找最大的一个满足w[j]>w[k]+w[k-1]的j(j<k),把合并后的值w[k]+w[k-1]插入w[j]的后面。
由于可以把从w[j+1]到w[i-2]的石子看成一个整体w[mid],现在考虑三堆石子的情况：w[j],w[mid],temp(w[i]+w[i-1]), 因为temp<w[j] ,因此不管怎样都是w[mid]和temp先合并, 所以temp值插入w[j]的后面后答案不会改变。
本来这个算法的原复杂度是O(n^2)，加上了平衡树优化的时间复杂度是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)的算法上，少数人提到了四边形不等式，但全部没有四边形不等式的详细证明，而且也没有讲解GarsiaWachs算法的题解。所有希望大家能在学习OI的时候，一直保持着对新知识的求知精神。