P1880 [NOI1995]石子合并

https://www.luogu.org/problemnew/show/P1880
在一个圆形操场的四周摆放N堆石子,现要将石子有次序地合并成一堆.规定每次只能选相邻的2堆合并成新的一堆，并将新的一堆的石子数，记为该次合并的得分。

试设计出1个算法,计算出将N堆石子合并成1堆的最小得分和最大得分.

输入输出格式

输入格式：

数据的第1行试正整数N,1≤N≤100,表示有N堆石子.第2行有N个数,分别表示每堆石子的个数.

输出格式：

输出共2行,第1行为最小得分,第2行为最大得分

https://www.lucien.ink/archives/142/
https://www.cnblogs.com/ehznehc/p/9801249.html

一、贪心

贪心只能处理“任取两堆”，而不能处理“相邻两堆”。任取两堆的题目就是 合并果子。

二、划分阶段

本题是区间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

基础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直接联系，完美避免了上述情况。

详情见代码。

七、代码

码风丑陋勿喷，没有优化勿喷。

另外，以此题的数据范围完全用不到四边形不等式这类的高档算法。

    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]);
    //选择最大（小）值
    }

https://blog.csdn.net/SunPeishuai/article/details/81772406
首先，要计算合并的最大值、最小值，既然是动态规划，我们需要洞悉其中一些关联且确定的状态。

以下以最大值为例。

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

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

这样我们可以定义状态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<j<=N。

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。这样，就能保证地推的正确。



    for(int i=1;i<=n+n;i++) 
    { 
        scanf("%d",&num[i]); 
        num[i+n]=num[i]; 
        s[i]=s[i-1]+num[i]; 
    } 
    for(int p=1;p<n;p++) 
    { 
        for(int i=1,j=i+p;(j<n+n) && (i<n+n);i++,j=i+p) 
        { 
            f2[i][j]=999999999; 
            for(int k=i;k<j;k++) 
            { 
                f1[i][j] = max(f1[i][j], f1[i][k]+f1[k+1][j]+d(i,j)); 
                f2[i][j] = min(f2[i][j], f2[i][k]+f2[k+1][j]+d(i,j)); 
            } 
        } 
    } 
    minl=999999999; 
    for(int i=1;i<=n;i++) 
    { 
        maxl=max(maxl,f1[i][i+n-1]); 
        minl=min(minl,f2[i][i+n-1]); 
    }



    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
        w[i+n]=w[i];
    }
    for(int i=1;i<=2*n;i++)
    {
        sum[i]=sum[i-1]+w[i];
    }
    for(int len=2;len<=n;len++)///区间长度
    for(int i=1;i<=n*2-len;i++)///这里要注意
    {             
       int j=i+len-1;
       dpmin[i][j]=1e9;
       for(int k=i;k<j;k++)///区间内的任意位置
       {
           dpmin[i][j]=min(dpmin[i][j],dpmin[i][k]+dpmin[k+1][j]+sum[j]-sum[i-1]);
           dpmax[i][j]=max(dpmax[i][j],dpmax[i][k]+dpmax[k+1][j]+sum[j]-sum[i-1]);
       }
    }
    int maxx=0;
    int minn=100000000;
    for(int i=1;i<=n;i++)
    {
        minn=min(minn,dpmin[i][i+n-1]);
        maxx=max(maxx,dpmax[i][i+n-1]);
    }