P4481 bjwc2018 序列合并 题解

· · 题解

虽然说挺水的，但是这是我的童年阴影，所以还是写个题解吧（

直接dp。设 g(l,r) 表示区间 l,...,r 合并成一个点的答案，dp(l,r,i) 表示区间 l,...,r 分成 i 段，每一段合并成一个点的答案，g 的转移枚举分了多少段，dp 的转移枚举最后一段。复杂度 O(n^4)，常数小的吓人，直接冲就过了。滚一下 dp，空间是 O(n^2) 的。

#include<stdio.h>
#include<string.h>

inline int min(int x,int y){ return x<y?x:y; }

int n,L,R;
int dp[302][302],g[302][302];
int a[302],pre[302];

int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d%d",&n,&L,&R);
        for(int i=1;i<=n;i++) scanf("%d",&a[i]),pre[i]=pre[i-1]+a[i];
        memset(g,0x3f,sizeof(g));
        for(int i=1;i<=n;i++) g[i][i]=0;
        for(int l=n;l>=1;l--)
        {
            memset(dp,0x3f,sizeof(dp));
            dp[l-1][0]=0;
            for(int r=l;r<=n;r++)
            {
                for(int i=1;i<=r-l+1&&i<=R;i++)
                    for(int p=r;p>=l;p--)
                        dp[r][i]=min(dp[r][i],dp[p-1][i-1]+g[p][r]);
                for(int i=L;i<=R;i++) g[l][r]=min(g[l][r],dp[r][i]+pre[r]-pre[l-1]);
                dp[r][1]=min(dp[r][1],g[l][r]);
            }
        }
        printf("%d\n",g[1][n]==0x3f3f3f3f?0:g[1][n]);
    }
    return 0;
}