字符合并

Time Limit: 20 Sec Memory Limit: 256 MB

Description

有一个长度为 n 的 01 串，你可以每次将相邻的 k 个字符合并，得到一个新的字符并获得一定分数。

得到的新字符和分数由这 k 个字符确定。你需要求出你能获得的最大分数。

Input

第一行两个整数n，k。接下来一行长度为n的01串，表示初始串。

接下来2^k行，每行一个字符ci和一个整数wi，

ci表示长度为k的01串连成二进制后按从小到大顺序得到的第i种合并方案得到的新字符,

wi表示对应的第i种方案对应获得的分数。

Output

输出一个整数表示答案

Sample Input

3 2
　101
　1 10
　1 10
　0 20
　1 30

Sample Output

40

HINT

1<=n<=300 ,0<=ci<=1, wi>=1, k<=8

Solution

我们显然考虑区间DP，再状态压缩一下，f[l][r][opt]表示[l, r]合成了opt的最大价值。

如果一个区间长度为len的话，最后合完会长度会变为len % (k - 1)。

转移的本质是把长度为k的区间变成0/1，分情况处理。

先枚举每一个断点pos，表示我们要把**[pos, r]合成一个0/1**，那么就要保证(r - pos + 1) % (k - 1) = 1，否则我们DP的时候，会把000看做是0一样转移，导致不能合成为一个0/1的合成了。

若len % (k -1) = 1，则合成完会剩下一个数，我们判断一下**[l, r]能否合成一个opt的状态，若可以，则f[l][r][c[opt]] = max(f[l][r][opt] + val[opt])。注意要先拿一个变量记录下来**，不能直接更新，否则会出现0状态更新了1，然后1又用0更新了的情况，导致答案过大。

最后答案显然就是max(f[1][n][opt])。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include<bits/stdc++.h>
using namespace std;
typedef long long s64;

const int ONE = 305;
const int MOD = 1e9 + 7;

int n, k;
int total;
int a[ONE];
char s[ONE];
int c[ONE], val[ONE];
s64 f[ONE][ONE][ONE];
s64 Ans;

int get()
{
    int res=1,Q=1;  char c;
    while( (c=getchar())<48 || c>57)
        if(c=='-')Q=-1;
    if(Q) res=c-48;
    while((c=getchar())>=48 && c<=57)
        res=res*10+c-48;
    return res*Q;
}

int main()
{
    n = get();  k = get(); total = (1 << k) - 1;

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= n; j++)
            for(int opt = 0; opt <= total; opt++)
                f[i][j][opt] = -1;

    scanf("%s", s + 1);
    for(int i = 1; i <= n; i++)
        a[i] = s[i] - '0', f[i][i][a[i]] = 0;

    for(int i = 0; i <= total; i++)
        c[i] = get(), val[i] = get();

    for(int l = n; l >= 1; l--)
        for(int r = l; r <= n; r++)
        {
            if(l == r) continue;

            for(int pos = r - 1; pos >= l; pos -= k - 1)
                for(int opt = 0; opt <= total; opt++)
                {
                    if(f[l][pos][opt] == -1) continue;
                    if(f[pos + 1][r][0] != -1 && (opt << 1) <= total)
                        f[l][r][opt << 1] = max(f[l][r][opt << 1], f[l][pos][opt] + f[pos + 1][r][0]);
                    if(f[pos + 1][r][1] != -1 && (opt << 1 | 1) <= total)
                        f[l][r][opt << 1 | 1] = max(f[l][r][opt << 1 | 1], f[l][pos][opt] + f[pos + 1][r][1]);
                }

            if((r - l + 1) % (k - 1) == 1 || k == 2)
            {
                s64 A = -1, B = -1;
                for(int opt = 0; opt <= total; opt++)
                    if(f[l][r][opt] != -1)
                    {
                        if(c[opt] == 0) A = max(A, f[l][r][opt] + val[opt]);
                        if(c[opt] == 1) B = max(B, f[l][r][opt] + val[opt]);
                    }

                f[l][r][0] = max(f[l][r][0], A);
                f[l][r][1] = max(f[l][r][1], B);
            }
        }

    for(int opt = 0; opt <= total; opt++)
        Ans = max(Ans, f[1][n][opt]);

    printf("%lld", Ans);

}