题意:给定一圈石子,将相邻的两堆石子合并,花费为合并后的石子数。给定一开始每一堆石子的个数,求合并的最小花费。(石子堆数<=1000)

分析:

由于是一圈石子,所以我们将其倍增以消除环的影响,然后很自然可以得出状态转移方程:设 f(i,j) 表示从 i 到 j 的石子合并的最小花费,sum[i][j] 表示从 i 到 j 的石子共有多少个 (程序中用前缀和)。
$$
f(i,j)=min(f(i,k)+f(k+1,j)+sum[i][j])
$$
但是这是 O(n3) 的算法。所以我们需要优化。
注意到 sum[i][j] 满足四边形关系,包含单调关系,所以 f 一定满足四边形不等式。由此,我们再用一个数组 s[i][j] 表示区间 f[i,j] 是通过 k=s[i][j] 使得 f[i][j] 最小的,那么状态转移方程可以变为:

$$
f(i,j)=min(f(i,k)+f(k+1,j)+sum[i][j]),s[i][j-1]\leq k\leq s[i+1][j]
$$


#include <cstdio>
#include <cstring>
using namespace std;
#define MX 2002
#define min(a,b) a<b?a:b
int a[MX],n,f[MX][MX],s[MX][MX],sum[MX];
int main()
{
    while(~scanf("%d",&n))
    {
        memset(f,0x4f,sizeof(f));
        for(int i=1;i<=n;++i)scanf("%d",&a[i]),a[n+i]=a[i];
        for(int i=1;i<=n<<1;++i)sum[i]=sum[i-1]+a[i];
        for(int i=1;i<=n<<1;++i)s[i][i]=i,f[i][i]=0;
        for(int l=1;l<=n;++l)
            for(int i=1;i+l<=n*2;++i)
                for(int k=s[i][i+l-1],j=i+l;k<=s[i+1][j];++k)
                    if(f[i][k]+f[k+1][j]+sum[j]-sum[i-1]<f[i][j])
                        f[i][j]=f[i][k]+f[k+1][j]+sum[j]-sum[i-1],s[i][j]=k;
        int mx=1<<30;
        for(int i=1;i<=n+1;++i)mx=min(mx,f[i][i+n-1]);
        printf("%d\n",mx);
    }
    return 0;
}
分类: 文章

2 条评论

van · 2018年2月25日 11:38 上午

dalao!

    konnyakuxzy · 2018年2月25日 4:11 下午

    重庆 Dalao Orz
    %%%%%
    您这:

    • 用 van♂样作为昵称
    • 用某插画交♂流网站作为个人网站

    啧,我还是没有删除您的评论哒,只是把您的个人♂网站链接删啦
    免得教坏小朋友
    233333

回复 van 取消回复

Avatar placeholder

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