题解 P3736 【[HAOI2016]字符合并】

· · 题解

这道题我觉得真实难度应该在省选/NOI-以下。

主要思路为区间dp+状压dp

由题目的k<=8考虑使用状态压缩。

为了得到最大的分数我们应该尽量合并数字到不能合并为止，于是最终得到的01串中的每一个数字 展开（还原后）是一系列不相交的区间，我们考虑用区间dp的思维来转移状态。

我们用f[ i ][ j ][ t ]表示原串中第i到j个数字最终合并成t的状态的最大分数。

我们枚举中间的断点mid，（i<=mid<=j）,上文已证区间不相交，于是不妨使mid右边的子串合并成t的最后一位数字，mid左边的合并成其他位的数字。 因为能合并成1位数字的原串长度可以为1，k，2k-1......，所以我们每次将mid的值改变k-1即可。

另有一种特殊情况，即i到j恰好有k位数字，我们直接把它合并一次。用一个辅助数组存储最大值（直接修改f数组可能会导致修改后的数能够再修改其他数组元素，具体看代码理解一下）。

最后的答案就是f[ 1 ][ n ][所有状态]中的最大值啦。 由于wi的值可能很大，所以记得使用long long。

附代码：

#include<bits/stdc++.h>
#define N 310
#define K 8
#define inf (ll)1<<60
#define ll long long
using namespace std;

ll n,k,a[N],c[1<<K],w[1<<K],f[N][N][1<<K];

int main()
{
    scanf("%lld%lld",&n,&k);
    for (ll i=1;i<=n;i++) scanf("%1lld",&a[i]);
    for (ll i=0;i<(1<<k);i++) scanf("%lld%lld",&c[i],&w[i]);
    for (ll i=1;i<=n;i++)
     for (ll j=1;j<=n;j++)
      for (ll z=0;z<(1<<k);z++)
      f[i][j][z]=-inf;
    //读入及初始化 
    for (ll i=n;i>=1;i--)
      for (ll j=i;j<=n;j++)    
      //注意循环的正逆顺序，因为mid比j小，j正序枚举；mid比i大，i倒序枚举
      //(使状态转移时f[i][mid-1][..],f[mid][j][..]的值已被处理好) 
      { 
        if (i==j) { f[i][j][a[i]]=0;continue;}
        ll len=j-i;
        len%=k-1; if (!len) len=k-1;
        for (ll mid=j;mid>i;mid-=k-1)
        for (ll op=0;op<(1<<(len));op++)
        { f[i][j][op<<1]=max(f[i][j][op<<1],f[i][mid-1][op]+f[mid][j][0]);
          f[i][j][op<<1|1]=max(f[i][j][op<<1|1],f[i][mid-1][op]+f[mid][j][1]);

        }
        if (len==k-1) 
        {
            ll g[2];
            g[0]=g[1]=-inf;
            for (ll op=0;op<(1<<k);op++)
            g[c[op]]=max(g[c[op]],f[i][j][op]+w[op]);
            f[i][j][0]=g[0];f[i][j][1]=g[1];
        }
      }
      ll ans=-inf;
      for (ll i=0;i<(1<<k);i++) ans=max(ans,f[1][n][i]);
      printf("%lld",ans);
}