我还以为我状压很好。。。。。。
噗！！！
果然我区间很差。。。
f[i][j][s]表示i~j段，合并后的状态为s所得的最大收益
枚举i,j,k,s.
f[i][j][s<<1]=max(f[i][j][s<<1],f[i][k−1][s]+f[k][j][0])
f[i][j][s<<1|1]=max(f[i][j][s<<1|1],f[i][k−1][s]+f[k][j][1])
就这样……
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
#define N 350
#define LL long long
char ch[N];
int n,m,nxt[N],a[N],bit[10];
LL val[N],ans,f[N][N][1<<8],maxn[2];
using namespace std;
int main()
{
bit[0]=1;for(int i=1;i<=9;i++)bit[i]=bit[i-1]<<1;
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
ch[i]=getchar();
while(ch[i]!='0'&&ch[i]!='1')ch[i]=getchar();
a[i]=ch[i]-'0';
}
for(int i=0;i<bit[m];i++)
scanf("%d%lld",&nxt[i],&val[i]);
memset(f,-1,sizeof f);
for(int i=1;i<=n;i++)f[i][i][a[i]]=0;
for(int l=2;l<=n;l++){
for(int i=1;i<=n-l+1;i++){
int j=i+l-1,len=l;
while(len>=m)len-=m-1;
for(int k=j;k>i;k-=m-1){
for(int s=0;s<bit[len==1?m-1:len-1];s++){
if(f[i][k-1][s]!=-1){
if(f[k][j][0]!=-1)f[i][j][s<<1]=max(f[i][j][s<<1],f[i][k-1][s]+f[k][j][0]);
if(f[k][j][1]!=-1)f[i][j][s<<1|1]=max(f[i][j][s<<1|1],f[i][k-1][s]+f[k][j][1]);
}
}
}
if(len==1){
maxn[0]=maxn[1]=-1;
for(int s=0;s<bit[m];++s)
if(f[i][j][s]!=-1)
maxn[nxt[s]]=max(maxn[nxt[s]],f[i][j][s]+val[s]);
f[i][j][0]=maxn[0];f[i][j][1]=maxn[1];
}
}
}
for(int i=0;i<=bit[m-1];i++)ans=max(ans,f[1][n][i]);
printf("%lld\n",ans);
return 0;
}