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

· · 题解

你是不是还因为比样例大1而苦恼

你是不是还因为前缀和而焦虑

不要 9998 不要 998 只要 996

让某菌来拯救样例MIN值是44的苍生吧

言归正传

题目

在一个圆形操场的四周摆放着n 堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆,并将新的一堆石子数记为该次合并的得分。试设计一个算法,计算出将n堆石子合并成一堆的最小得分。

首先可以轻松排除贪心的可能

分析

这道题肯定要用区间DP

我们先只考虑直线的情况

假设只有2堆石子,显然只有1种合并方案

如果有3堆石子,则有2种合并方案,((1,2),3)和(1,(2,3))

如果有4堆石子,则有5种合并方案

(((1,2),3),4)、((1,(2,3)),4)、(1,((2,3),4))、(1,(2,(3,4)))、((1,2),(3,4))

如果有k堆石子呢?

不管怎么合并,总之最后总会归结为2堆,如果我们把最后两堆分开,左边和右边无论怎么合并,都必须满足最优合并方案,整个问题才能得到最优解。如下图

codevs上有一道题:1048 石子归并

题目是

有n堆石子排成一列,每堆石子有一个重量w[i], 每次合并可以合并相邻的两堆石子,一次合并的代价为两堆石子的重量和w[i]+w[i+1]。问安排怎样的合并顺序,能够使得总合并代价达到最小。

分析

设f[i][j]:区间[i,j]合并成一堆的最优值

可以推出动态规划方程为f[i][j]=f[i][k]+f[k+1][j]+cost[i,j]

阶段:len: 2 ~ n

状态:i: 1 ~ n – len + 1, j: i + len – 1

策略:k: i ~ j

所以时间复杂度为n^4

优化:预处理sum[i]表示前i堆石子总数量,则cost[i,j] = sum[j] – sum[i - 1],时间优化为n^3

分析图

鼠标作图极丑 恰好就可以打出如下代码

/*
作者:dayuanjun
题目:p1048 石子归并
*/
#include<bits/stdc++.h>
using namespace std;
int n;
int w[105];
int f[105][105];
int cost[105][105];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
    }
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++)
    for(int k=i;k<=j;k++)
    {
        cost[i][j]+=w[k];
    }
    for(int i=1;i<=n;i++)
    {
        f[i][i]=0;
    }
    for(int len=2;len<=n;len++)
    for(int l=1;l<=n-len+1;l++)
    {
        int r=l+len-1;
        for(int k=l;k<r;k++)
        {
            f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+cost[l][r]);
        }
    }
    printf("%d",f[1][n]);
    return 0;
}

然而这道题是一个环

所以

加上环怎么办?

断环为链:将长度为n的链复制一份接在后面,环的情况就是长度为2n的链中任意连续的长度为n的链。

for(int i=1;i<=n;i++)
{
    scanf("%d",&w[i]);
    w[i+n]=w[i];             
}

因为要求最大值,所以再开一个数组存最大值

#include<bits/stdc++.h>
using namespace std;
int n;
int w[205];
int f[205][205];
int ff[205][205];
int cost[205][205];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
        w[n+i]=w[i];
    }
    memset(f,0x3f,sizeof(f));
    for(int i=1;i<=n;i++)
    for(int j=i;j<=n;j++)
    for(int k=i;k<=j;k++)
    {
        cost[i][j]+=w[k];
    }
    for(int i=1;i<=n;i++)
    {
        f[i][i]=0;
        ff[i][i]=0;
    }
    for(int len=2;len<=n;len++)
    for(int l=1;l<=n-len+1;l++)
    {
        int r=l+len-1;
        for(int k=l;k<r;k++)
        {
            f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+cost[l][r]);
            ff[l][r]=max(ff[l][r],ff[l][k]+ff[k+1][r]+cost[l][r]);
        }
    }
    int ans1=0x7fffffff/2,ans2=0;
    for(int i=1;i<=n;i++) ans1=min(ans1,f[i][i+n-1]);
    for(int i=1;i<=n;i++) ans2=max(ans2,ff[i][i+n-1]);
    printf("%d\n%d",ans1,ans2);
    return 0;
}

然而 少年你天真了 颜色逐渐蒟蒻化

修改 ※

我们要注意,因为加了一圈,所以求前缀和的for循环不应该是1~n了,而应该是1~2n,如下

for(int i=1;i<=2*n;i++)
    for(int j=i;j<=2*n;j++)
    for(int k=i;k<=j;k++)
    {
        cost[i][j]+=w[k];
    }

同时在DP部分l也要循环到2*n

for(int len=1;len<n;len++)
    for(int l=1,r=l+len;r<n*2&&l<n*2;l++,r=l+len)
    {
        f[l][r]=0x7fffffff/2;
        for(int k=l;k<r;k++)
        {
            f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+cost[l][r]);
            ff[l][r]=max(ff[l][r],ff[l][k]+ff[k+1][r]+cost[l][r]);
        }
    }

代码如下

#include<bits/stdc++.h>
using namespace std;
int n;
int w[205];
int f[205][205];
int ff[205][205];
int cost[205][205];
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&w[i]);
        w[n+i]=w[i];
    }
    for(int i=1;i<=2*n;i++)
    for(int j=i;j<=2*n;j++)
    for(int k=i;k<=j;k++)
    {
        cost[i][j]+=w[k];
    }
    for(int i=1;i<=n;i++)
    {
        f[i][i]=0;
        ff[i][i]=0;
    }
    for(int len=1;len<n;len++)
    for(int l=1,r=l+len;r<n*2&&l<n*2;l++,r=l+len)
    {
        f[l][r]=0x7fffffff/2;
        for(int k=l;k<r;k++)
        {
            f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]+cost[l][r]);
            ff[l][r]=max(ff[l][r],ff[l][k]+ff[k+1][r]+cost[l][r]);
        }
    }
    int ans1=0x7fffffff/2,ans2=0;
    for(int i=1;i<=n;i++) ans1=min(ans1,f[i][i+n-1]);
    for(int i=1;i<=n;i++) ans2=max(ans2,ff[i][i+n-1]);
    printf("%d\n%d",ans1,ans2);
    return 0;
}

知乎 大源菌

b站源菌想吃木桶饭