思路

可能是个套路题,但是没见过...
第一眼觉得是个区间,但是中间的状态总是弄不清楚...
然后看了题解是状压+区间.
令表示为区间合并成字符串所获得的最大代价.
区间的划分有个优化就是,每次只能是这种才能形成,然后就行划分,当区间是这个长度的时候进行一次答案统计即可.

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=3e2+5,M=(1<<8);
char s[N];
ll w[M],c[M],g[2];
ll f[N][N][M];//从l到r合并成v的最大价值是多少.
int main()
{
    int n,k;
    scanf("%d%d",&n,&k);
    scanf("%s",s+1);
    for(int i=0;i<(1<<k);i++)
        scanf("%lld%lld",&c[i],&w[i]);
    memset(f,-0x3f,sizeof f);
    ll inf=-(0x3f3f3f3f);
    for(int i=1;i<=n;i++)   f[i][i][s[i]-'0']=0;
    for(int len=2;len<=n;len++)
    {
        for(int l=1;l<=n-len+1;l++)
        {
            int r=l+len-1;
            int x=(len-1)%(k-1);
            if(x==0)    x=k-1;
            for(int mid=r-1;mid>=l;mid-=(k-1))
            {
                for(int s=0;s<(1<<x);s++)
                {
                    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]);
                }
            }
            if(x==k-1)
            {
                g[0]=g[1]=inf;
                for(int i=0;i<(1<<k);i++)   g[c[i]]=max(g[c[i]],f[l][r][i]+w[i]);
                f[l][r][0]=g[0],f[l][r][1]=g[1];
            }
        }
    }
    ll ans=inf;
    for(int i=0;i<(1<<k);i++)
        ans=max(ans,f[1][n][i]);
    printf("%lld\n",ans);
    return 0;
}