BZOJ4565【HAOI2016】字符合并 <状压DP>

Problem

【HAOI2016】字符合并

Description

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

Input

第一行两个整数，。接下来一行长度为的串，表示初始串。接下来行，每行一个字符和一个整数，表示长度为的串连成二进制后按从小到大顺序得到的第种合并方案得到的新字符，表示对应的第种方案对应获得的分数。, , ,

Output

输出一个整数表示答案

Sample Input

Sample Output

标签：状压DP

Solution

这显然是一道状压（）
考虑用表示将字符序列表示为状态的最大分数。
初始状态为 ()
转移则将斩成两半和，，。
特别需要注意的是，当时（为题目中的），会刚好变为一个字符，因此不能像上面那样递推，应为(且可为)，(且可为)。

Code

#include <iostream>
#include <cstdio>
#include <cstring>
#define MAX_K 8
#define MAX_N 300
using namespace std;
typedef long long lnt;
char str[MAX_N+5];
int n, m, s[MAX_N+5], c[1<<MAX_K];
lnt w[1<<MAX_K], f[MAX_N+5][MAX_N+5][1<<MAX_K];
void upd(lnt &a, lnt b) {if (a < b)	a = b;}
int main() {
    scanf("%d%d%s", &n, &m, str), memset(f, -1, sizeof(f));
    for (int i = 0; i < (1<<m); i++)	scanf("%d%lld", c+i, w+i);
    for (int i = 1; i <= n; i++)	s[i] = str[i-1]-'0', f[i][i][s[i]] = 0;
    for (int l = 2; l <= n; l++)
        for (int s = 1, t = s+l-1; t <= n; t = ++s+l-1) {
            int tar = l-1;	while (tar >= m)	tar -= m-1;
            for (int mid = t-1; mid >= s; mid -= m-1)	for (int sta = 0; sta < (1<<tar); sta++) {
                if (~f[s][mid][sta] && ~f[mid+1][t][0])	upd(f[s][t][sta<<1], f[s][mid][sta]+f[mid+1][t][0]);
                if (~f[s][mid][sta] && ~f[mid+1][t][1])	upd(f[s][t][sta<<1|1], f[s][mid][sta]+f[mid+1][t][1]);
            }
            if (tar == m-1) {
                lnt g[2];	g[0] = g[1] = -1;
                for (int sta = 0; sta < (1<<m); sta++)
                    if (~f[s][t][sta])	upd(g[c[sta]], f[s][t][sta]+w[sta]);
                f[s][t][0] = g[0], f[s][t][1] = g[1];
            }
        }
    lnt ans = 0;	for (int i = 0; i < (1<<m); i++)	ans = max(ans, f[1][n][i]);	printf("%lld", ans);	return 0;
}