1767：字符合并

Description
有一个长度为 n 的 01 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。得到的新字
符和分数由这 k 个字符确定。你需要求出你能获得的最大分数。

Input
第一行两个整数n，k。接下来一行长度为n的01串，表示初始串。接下来2k行，每行一个字符ci和一个整数wi，ci
表示长度为k的01串连成二进制后按从小到大顺序得到的第i种合并方案得到的新字符,wi表示对应的第i种方案对应
获得的分数。1<=n<=300,0<=ci<=1,wi>=1,k<=8

Output

输出一个整数表示答案

Sample Input
3 2
101
1 10
1 10
0 20
1 30
Sample Output
40

【题解】

发现k很小，可以考虑状压。

定义f[i][j][s]表示原串第i到j个字符合成成状态s所获得最大的分数。

初值：

f[i][i][kai[i]]=0;其他=-inf。

转移：

考虑到一段数肯定合得越多越优，所以一段中肯定合得不能再合，剩下的数的个数就是hu=（len-1）%(k-1)。

所以枚举这一段的状态为0---(1<<hu)-1。

考虑到一段数肯定是从左边一个区间一个s1和右边一个区间s2合并而得，所以可以令右边的区间只剩下一个数，又是一个舒服的优化。

如果hu==0即剩下了k个数，则可以枚举每一个状态，f[i][j][c[s]]=f[i][j][s]+w[s]。

代码如下：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=305;
int n,k,kai[N],c[N],w[N],f[N][N][N];
inline int read()
{
    char c=getchar();
    int x=0,f=1;
    while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)) {x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return x*f;
}
signed main()
{
    n=read();k=read();
    for(int i=1;i<=n;i++) kai[i]=read();
    for(int i=0;i<(1<<k);i++) c[i]=read(),w[i]=read();
    for(int i=1;i<=n;i++)
    { 
        for(int l=0;l<(1<<k);l++)
            f[i][i][l]=-0x3f3f3f3f;
        f[i][i][kai[i]]=0;
    }
    for(int i=2;i<=n;i++)
    {
        for(int j=1;j+i-1<=n;j++)
        {
            int y=j+i-1;
            for(int l=0;l<(1<<k);l++) f[j][y][l]=-0x3f3f3f3f;
            int she=(i-1)%(k-1);
            if(!she) she=k-1;
            for(int l=y;l>j;l-=(k-1))
            {
                for(int s=0;s<1<<she;s++)
                    f[j][y][s<<1]=max(f[j][y][s<<1],f[j][l-1][s]+f[l][y][0]),
                    f[j][y][s<<1|1]=max(f[j][y][s<<1|1],f[j][l-1][s]+f[l][y][1]);
            }
            if(she==k-1)
            {
                int hu[2];hu[0]=hu[1]=-0x3f3f3f3f;
                for(int s=0;s<(1<<k);s++)
                    hu[c[s]]=max(hu[c[s]],f[j][y][s]+w[s]);
                f[j][y][0]=hu[0];f[j][y][1]=hu[1];
            }
        }
    }
    int ans=-0x3f3f3f3f;
    for(int i=0;i<1<<k;i++) ans=max(ans,f[1][n][i]);
    cout<<ans;
}