题目描述
有一个长度为 $n$ 的 $01$ 串,你可以每次将相邻的 $k$ 个字符合并,得到一个新的字符并获得一定分数。得到的新字符和分数由这 $k$ 个字符确定。你需要求出你能获得的最大分数。
数据范围
$1 \leq n \leq 300, \ 0 \leq c_i \leq 1, \ w_i \geq 1, \ k \leq 8$
题解
数据范围较小,考虑区间 $dp$ , $f_{l,r,s}$ 表示 $[l,r]$ 最后合并成状态 $s$ 的最大分数,可以通过 $l,r$ 知道 $s$ 的长度
考虑转移,发现只要枚举中间点 $x$ ,让 $[l,x]$ 合成前 $s-1$ 位, $(x,r]$ 合成最后一位即可
注意当 $s$ 的长度为 $0$ 时,将其变为 $k$ 即可
代码
#include <bits/stdc++.h> #define LL long long using namespace std; const int N=305; int n,k,a[N],b[N],c[N]; LL f[N][N][N],ans=-2e18; char s[N]; int main(){ scanf("%d%d%s",&n,&k,s+1); for (int i=1;i<=n;i++) c[i]=s[i]^48; for (int i=0;i<(1<<k);i++) scanf("%d%d",&a[i],&b[i]); for (int i=1;i<=n;i++) for (int j=1;j<=n;j++) for (int l=0;l<(1<<k);l++) f[i][j][l]=-2e18; for (int i=1;i<=n;i++) f[i][i][c[i]]=0; for (int len=1;len<n;len++){ for (int r,v,l=1;l+len<=n;l++){ r=l+len;v=(r-l)%(k-1)+1; if (v==1){ for (int w=0;w<(1<<k);w++) for (int x=r-1;x>=l;x-=k-1) f[l][r][a[w]]=max(f[l][r][a[w]],f[l][x][w>>1]+f[x+1][r][w&1]+b[w]); } else{ for (int w=0;w<(1<<v);w++) for (int x=r-1;x>=l;x-=k-1) f[l][r][w]=max(f[l][r][w],f[l][x][w>>1]+f[x+1][r][w&1]); } } } for (int i=0;i<(1<<k);i++) ans=max(ans,f[1][n][i]); return printf("%lld\n",ans),0; }