[Haoi2016]字符合并 - NekoMio's Blog

题目描述#

有一个长度为 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])

1
#include <cstdio>
2
#include <cstring>
3
#include <bitset>
4
using namespace std;
5
int a[400], c;
6
int s[1 << 8];
7
long long w[1 << 8], f[305][305][1 << 8], INF, ans;
8
int main()
9
{
10
    // freopen("merge.in","r",stdin);
11
    // freopen("merge.out","w",stdout);
12
    int n, k;
13
    scanf("%d%d", &n, &k);
14
    for (int i = 1; i <= n; i++)
15
        scanf("%1d", &a[i]);
16
    for (int i = 0; i < (1 << k); i++)
17
        scanf("%d%lld", &s[i], &w[i]);
18
    memset(f, 0x80, sizeof(f));
19
    memset(&INF, 0x80, sizeof(INF));
20
    for (int i = 1; i <= n; i++)
21
        f[i][i][a[i]] = 0;
22
    for (int l = 2; l <= n; l++)
23
    {
24
        for (int i = 1; i <= n - l + 1; i++)
25
        {
26
            int j = i + l - 1;
27
            int len = j - i;
28
            while (len >= k)
29
                len -= k - 1;
30
            for (int m = j; m > i; m -= k - 1)
31
            {
32
                for (int S = 0; S < (1 << len); S++)
33
                {
34
                    if (f[i][m - 1][S] != INF)
35
                    {
36
                        if (f[m][j][0] != INF)
37
                            f[i][j][S << 1] = max(f[i][j][S << 1], f[i][m - 1][S] + f[m][j][0]);
38
                        if (f[m][j][1] != INF)
39
                            f[i][j][S << 1 | 1] = max(f[i][j][S << 1 | 1], f[i][m - 1][S] + f[m][j][1]);
40
                    }
41
                }
42
            }
43
            if (len == k - 1)
44
            {
45
                long long g[2];
46
                g[0] = g[1] = INF;
47
                for (int S = 0; S < (1 << k); S++)
48
                    if (f[i][j][S] != INF)
49
                        g[s[S]] = max(g[s[S]], f[i][j][S] + w[S]);
50
                f[i][j][0] = g[0];
51
                f[i][j][1] = g[1];
52
            }
53
        }
54
    }
55
    for (int i = 0; i < (1 << k); i++)
56
        ans = max(ans, f[1][n][i]);
57
    printf("%lld\n", ans);
58
    //while(1);
59
}