[HAOI2016]字符合并

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

有一个长度为 n 的 01 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。得到的新字符和分数由这 k
个字符确定。你需要求出你能获得的最大分数。 输入描述: 第一行两个整数n，k。 接下来一行长度为n的01串，表示初始串。
接下来2k行，每行一个字符ci和一个整数wi，ci
表示长度为k的01串连成二进制后按从小到大顺序得到的第i种合并方案得到的新字符,wi表示对应的第i种方案对应获得的分数。 1 ≤ n ≤
300,0 ≤ ci ≤ 1,wi ≥ 1, k ≤ 8

输出描述:

输出一个整数表示答案

示例1
输入
复制

3 2
101
1 10
1 10
0 20
1 30

输出
复制

40

题解：

一开始愣是没看懂题意
长度为k的01串连成二进制后按从小到大顺序，这句话我们用样例来讲就是
00，01，10，11这四个从小到大排列
分数分别是输入的10,10,20,30

参考题解
区间dp+状压dp
dp[l][r][s]表示区间[l,r]合并为s的最小代价
经过推到可以得到：当串的长度为 lenlen 时，最后该串的长度为 (len-1) mod (k-1)+1
区间dp问题就是枚举中间的端点，把区间[l,r]拆分成[l,mid]和[mid+1,r]

状态定义：

f[l][r][S<<1]=max(f[l][r][S<<1],f[l][mid][S]+f[mid+1][r][0]);
f[l][r][S<<1|1]=max(f[l][r][S<<1|1],f[l][mid][S]+f[mid+1][r][1]);

区间[mid+1,r]相当于已经合并完了，因为合并完的值就是0或1，直接加到前面区间[l,mid]上，f[l][mid][S]则是看[l,mid]这段区间合并成多少

当区间长度正好为k时，就直接合并，更新数据（用两个临时变量先储存）
g[c[S]]=max(g[c[S]],f[l][r][S]+w[S]);
区间[l,r]合并为c[S]的最大值，然后
f[l][r][0]=g[0];f[l][r][1]=g[1];
g[]就是临时变量

代码：

#include <bits/stdc++.h>
using namespace std;
#define LL long long
#define INF 0x3f3f3f3f
LL f[310][310][(1<<8)+20];
char s[310];
int b[(1<<8)+20];
LL c[(1<<8)+20];
int main()
{
  int n,m,k,i,j;
  scanf("%d%d",&n,&k);
  scanf("%s",s+1);
  for(i=0; i<(1<<k); ++i)
    scanf("%d%lld",b+i,c+i);
  memset(f,-INF,sizeof(f));
  LL inf=f[0][0][0];
  for(i=1; i<=n; ++i) f[i][i][s[i]-'0']=0;
  for(int len=2; len<=n; ++len)
  {
    for(i=1; i+len-1<=n; ++i)
    {
      j=i+len-1;
      int l=(j-i)%(k-1);
      if(!l) l=k-1;
      for(int las=j; las>=i; las-=k-1)
      {
        for(int S=0; S<(1<<l); ++S)
        {
          if(f[i][las-1][S]==inf) continue;
          if(f[las][j][0]!=inf)
            f[i][j][S<<1]=max(f[i][j][S<<1],f[i][las-1][S]+f[las][j][0]);
          if(f[las][j][1]!=inf);
          f[i][j][S<<1|1]=max(f[i][j][S<<1|1],f[i][las-1][S]+f[las][j][1]);
        }
      }
      if(l==k-1)
      {
        LL g[2]= {inf,inf};
        for(int S=0; S<(1<<k); ++S)
        {
          if(f[i][j][S]!=inf)
          {
            g[b[S]]=max(g[b[S]],f[i][j][S]+c[S]);
          }
        }
        f[i][j][0]=g[0];
        f[i][j][1]=g[1];
      }
    }
  }
  LL ans=0;
  int l=n%(k-1)?n%(k-1):k-1;
  for(i=0; i<(1<<l); ++i)
    ans=max(ans,f[1][n][i]);
  cout<<ans<<endl;
  return 0;
}