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

· · 题解

显然，对于每一堆已经合并了的石子的阶段性分数，我们都可以将其拆分为来自两个子堆的分数值+它们的石子总和，这就是题目给出的定义。

因为只能合并相邻的两堆石子，所以我们在拆分石子堆时，相当于对它所涵盖的最初的石子堆进行枚举，从这个堆开始将其分成两半，取最大或最小值。

于是有状态转移方程: dp(i~j)=(min/max)(dp(i~k)+dp(k+1~j)+a[i]+...+a[j]);

dp(i,j)是第i～j堆石子全部合并后的最大的或最小的分数 k是拆分石子堆的分界点， 这对于最大值或最小值均成立。

但这是不够的，因为我们目前的算法只适用于队列形式的石子合并，而题目中要求的是环状的，再对从合并了队末与队头的石子堆进行特判将会十分复杂。

我们的思想还可以更解放——高中物理必修2

其实我们把区间的长度拓宽一倍，就完全可以解决这个问题。此时我们的目的状态就不再是dp[1][m]了，而是(max/min)(dp[i][i+m-1]),i属于[1,m]中的正整数,初始化前缀和时也将前缀和数组的长度拓宽一倍即可。

代码如下：

#include <bits/stdc++.h>

using namespace std;
//防止爆炸，全开LL
long long MAXN=(1LL<<60);
long long MAXX,MINN=MAXN;
long long f[212][212],dp[212][212];
long long a[212],qz[212];
long long qj;
int m,i,j,k;

long long max0(long long xx,long long yy){
    return xx>yy?xx:yy;
}

long long min0(long long xx,long long yy){
    return xx<yy?xx:yy;
}

int main(){
    scanf("%d",&m);
    for(i=1;i<=210;i++)
        for(j=i;j<=210;j++)
        {
            dp[i][j]=MAXN;//因为计算的是最小值，所以初始化最小值时一定要赋值为无穷大
        }
    for(i=1;i<=m;i++)
    {
        scanf("%lld",&a[i]);
        qz[i]=a[i]+qz[i-1];//前缀和
        dp[i][i]=0;//对于区间[i,i],它并不需要合并,因此赋值为0
    }
    for(i=m+1;i<=2*m;i++)//拓宽范围
    {
        qz[i]=qz[i-1]+a[i-m];
        dp[i][i]=0;
    }

    for(i=1;i<=m-1;i++)//枚举区间长度，这样才能保证拆分区间前，所有长度比它小的区间都以被处理完毕了
    {
        for(j=1;j<=2*m-1;j++)//枚举区间左端
        {
            if(j+i>2*m) break;//直接跳出去，因为接下来的循环是无意义的了
            qj=qz[i+j]-qz[j-1];//减少计算次数
            for(k=j;k<i+j;k++)
            {
                f[j][i+j]=max0(f[j][i+j],f[j][k]+f[k+1][i+j]+qj);//转移方程
            }
        }
    }
    for(i=1;i<=m-1;i++)//这里同上
    {
        for(j=1;j<=2*m-1;j++)
        {
            if(i+j>2*m) break;
            qj=qz[i+j]-qz[j-1];
            for(k=j;k<i+j;k++)
            {
                dp[j][i+j]=min0(dp[j][i+j],dp[j][k]+dp[k+1][i+j]+qj);
            }
        }
    }
    for(i=1;i<=m;i++)//取最大值
    MAXX=max0(MAXX,f[i][i+m-1]);
    for(i=1;i<=m;i++)//取最小值
    MINN=min0(MINN,dp[i][i+m-1]);
    printf("%lld\n%lld",MINN,MAXX);//输出
    return 0;
}