[Haoi2016]字符合并

题目描述

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

输入

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

输出

输出一个整数表示答案

样例输入

3 2
101
1 10
1 10
0 20
1 30

样例输出

40

//第3行到第6行表示长度为2的4种01串合并方案。00->1,得10分，01->1得10分，10->0得20分，11->1得30分。

题解

令f[i][j][S]表示将i~j这一段消到S这个状态能获得的最大得分。
f[i][j][S<<1]=max(f[i][j][S<<1],f[i][m−1][S]+f[m][j][0])
f[i][j][S<<1|1]=max(f[i][j][S<<1|1],f[i][m−1][S]+f[m][j][1])

#include <cstdio>
#include <cstring>
#include <bitset>
using namespace std;
int a[400], c;
int s[1 << 8];
long long w[1 << 8], f[305][305][1 << 8], INF, ans;
int main()
{
    // freopen("merge.in","r",stdin);
    // freopen("merge.out","w",stdout);
    int n, k;
    scanf("%d%d", &n, &k);
    for (int i = 1; i <= n; i++)
        scanf("%1d", &a[i]);
    for (int i = 0; i < (1 << k); i++)
        scanf("%d%lld", &s[i], &w[i]);
    memset(f, 0x80, sizeof(f));
    memset(&INF, 0x80, sizeof(INF));
    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;
            int len = j - i;
            while (len >= k)
                len -= k - 1;
            for (int m = j; m > i; m -= k - 1)
            {
                for (int S = 0; S < (1 << len); S++)
                {
                    if (f[i][m - 1][S] != INF)
                    {
                        if (f[m][j][0] != INF)
                            f[i][j][S << 1] = max(f[i][j][S << 1], f[i][m - 1][S] + f[m][j][0]);
                        if (f[m][j][1] != INF)
                            f[i][j][S << 1 | 1] = max(f[i][j][S << 1 | 1], f[i][m - 1][S] + f[m][j][1]);
                    }
                }
            }
            if (len == k - 1)
            {
                long long g[2];
                g[0] = g[1] = INF;
                for (int S = 0; S < (1 << k); S++)
                    if (f[i][j][S] != INF)
                        g[s[S]] = max(g[s[S]], f[i][j][S] + w[S]);
                f[i][j][0] = g[0];
                f[i][j][1] = g[1];
            }
        }
    }
    for (int i = 0; i < (1 << k); i++)
        ans = max(ans, f[1][n][i]);
    printf("%lld\n", ans);
    //while(1);
}