解题报告 P1880 [NOI1995]石子合并

题目内容

P1880

大意:n 堆石子摆一圈,每次选相邻的两堆合在一起,并将新的一堆的石子数,记为该次合并的得分。求合并成 1 堆后的最大和最小得分。

解题思路

区间 dp 模板题

像这类满足可以区间合并最优的 dp,一般都是进行分段分段的求阶段性最优值,再依次合并。这类问题一般都是枚举一个区间长度 l,然后依次枚举左右端点,再枚举中间的断点 k,进行子问题的合并。比如这题,令 f(i,j) 表示在区间 [l,r] 上进行合并能达到的最大得分,转移方程就是

f(i,j)=\max_{k\in[l,r)}\lbrace f(i,j),f(i,k)+f(k+1,r)+sum(i,j)\rbrace

其中 sum(i,j) 表示这一段的石子数量的区间和,可以前缀和预处理达到

然后由于这个题中是一个环,所以考虑把这个环延长成两倍,然后不要忘记所有流程都扩成两倍,然后最后统计答案的时候遍历一遍即可。时间复杂度 O(n^3) (一层枚举区间长度,一层枚举区间左右端点,一层枚举中间断点 k

#include <cstdio>

const int maxn=105;
int a[maxn<<1],f1[maxn<<1][maxn<<1],f2[maxn<<1][maxn<<1],n,s[maxn<<1];
//a为每一堆的数量,f1为最大值,f2为最小值,s为石子堆数的前缀和

inline int max(int a,int b)//不想用algorithm库的
{
    return a>b?a:b;
}

inline int min(int a,int b)
{
    return a<b?a:b;
}

int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",a+i);
        a[n+i]=a[i];//记得copy一份
    }
    for(int i=1;i<=n<<1;i++)
        s[i]=s[i-1]+a[i];//前缀和处理
    for(int l=1;l<n;l++)//枚举区间的长度,这里的l其实是实际长度-1
        for(int i=1,j=i+l;j<n<<1&&i<n<<1;i++,j=i+l)//枚举i,j,注意i和j之间的宽度是固定的
        {
            f2[i][j]=0x3f3f3f3f;//先给他一个无穷大
            int d=s[j]-s[i-1];//后面要用到的就先处理了
            for(int k=i;k<j;k++)//枚举中间断点k
            {
                f1[i][j]=max(f1[i][j],f1[i][k]+f1[k+1][j]+d);
                f2[i][j]=min(f2[i][j],f2[i][k]+f2[k+1][j]+d);
            }
        }
    int ans1=0,ans2=0x3f3f3f3f;
    for(int i=1;i<n;i++)//最后统计一波答案
    {
        ans1=max(ans1,f1[i][i+n-1]);
        ans2=min(ans2,f2[i][i+n-1]);
    }
    printf("%d\n%d\n",ans2,ans1);//注意先最小后最大
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注