题意:给定一圈石子,将相邻的两堆石子合并,花费为合并后的石子数。给定一开始每一堆石子的个数,求合并的最小花费。(石子堆数<=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

发表评论

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

你是机器人吗? =。= *