传送门
当看到那个k≤8k\le 8k≤8的时候就知道需要状压了。
状态定义：f[i][j][k]f[i][j][k]f[i][j][k]表示区间[i,j][i,j][i,j]处理完之后的状态为kkk时的最大贡献。
由于每次合并会减少K−1K-1K−1个，因此0<k≤K−10<k\le K-10<k≤K−1。
然后转移的时候不用一个一个转移。
两次转移的断点的距离需要保证是k−1k-1k−1，因为这样子肯定不必之前距离不为k−1k-1k−1时更优。
注意处理特殊情况（整个区间刚好可以被消玩）
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
int n,k,up,s[305],sta[260];
ll f[305][305][260],w[260],ans=0;
char S[305];
inline ll read(){
ll ans=0;
char ch=getchar();
while(!isdigit(ch))ch=getchar();
while(isdigit(ch))ans=(ans<<3)+(ans<<1)+(ch^48),ch=getchar();
return ans;
}
int main(){
n=read(),k=read(),up=1<<k,memset(f,-1,sizeof(f));
scanf("%s",S+1);
for(int i=1;i<=n;++i)s[i]=S[i]-'0';
for(int i=0;i<up;++i)sta[i]=read(),w[i]=read();
for(int i=1;i<=n;++i)f[i][i][s[i]]=0;
for(int Len=1;Len<n;++Len)
for(int l=1;l+Len<=n;++l){
int r=l+Len,len=Len;
while(len>k-1)len-=k-1;
for(int m=r;m>l;m-=k-1)for(int stat=0;stat<(1<<len);++stat)
if(~f[l][m-1][stat]){
if(~f[m][r][0])f[l][r][stat<<1]=max(f[l][r][stat<<1],f[l][m-1][stat]+f[m][r][0]);
if(~f[m][r][1])f[l][r][stat<<1|1]=max(f[l][r][stat<<1|1],f[l][m-1][stat]+f[m][r][1]);
}
if(len==k-1){
ll tmp[2];
tmp[0]=tmp[1]=-1;
for(int stat=0;stat<up;++stat)if(~f[l][r][stat])tmp[sta[stat]]=max(tmp[sta[stat]],f[l][r][stat]+w[stat]);
f[l][r][0]=tmp[0],f[l][r][1]=tmp[1];
}
}
for(int i=0;i<up;++i)ans=max(ans,f[1][n][i]);
cout<<ans;
return 0;
}