「BZOJ 4565」「HAOI 2016」字符合并「区间状压DP」

题意

给一个长度为\(n(\leq 300)\)的\(01\)串，每次可以把\(k(\leq 8)\)个相邻字符合并，得到新字符和一定分数，最大化最后的得分

题解

考虑设计dp：\(dp[S][i][j]\)表示区间\([i, j]\)合并为\(S\)，最大得分是多少。

这么考虑一定是不遗漏的。如果\([i, j]\)留下来的区间长度\(>k\)，那这个合并方案一定会在包含它的大区间计算到，所以我们只考虑能合并都合并完的情况

枚举缩完最后一个位是啥，这对应\([i, j]\)的一个长度\(\bmod k-1\)为\(1\)后缀

然后再考虑这个区间缩成一个字符的情况。由于顺序混乱（比如\(0\)更新\(1\)，\(1\)又更新\(0\)），拿临时数组存，最后再赋值回去

#include <algorithm>

#include <cstring>

#include <cstdio>

using namespace std;

typedef long long ll;

const int N = 310;

int n, k, c[1 << 8], la[N];

ll w[1 << 8], g[2], dp[1 << 8][N][N];

char s[N];

void upd(ll &x, ll y) { x = max(x, y); }

int main() {

	scanf("%d%d%s", &n, &k, s + 1);

	for(int i = 0; i < (1 << k); i ++) scanf("%d%lld", c + i, w + i);

	for(int i = 1, j; i <= n; i ++) {

		for(j = i; j >= k; j = j - k + 1);

		la[i] = j;

	}

	memset(dp, -1, sizeof dp);

	for(int i = 1; i <= n; i ++) dp[s[i] -= '0'][i][i] = 0;

	for(int i = n - 1; i >= 1; i --) {

		for(int j = i + 1; j <= n; j ++) {

			for(int u = j; u > i; u -= k - 1) {

				for(int S = 0; S < (1 << la[u - i]); S ++) if(~ dp[S][i][u - 1]) {

					if(~ dp[0][u][j]) upd(dp[S << 1][i][j], dp[S][i][u - 1] + dp[0][u][j]);

					if(~ dp[1][u][j]) upd(dp[S << 1 | 1][i][j], dp[S][i][u - 1] + dp[1][u][j]);

				}

			}

			if(la[j - i + 1] == 1) {

				g[0] = g[1] = -1;

				for(int S = 0; S < (1 << k); S ++) if(~ dp[S][i][j]) {

					upd(g[c[S]], dp[S][i][j] + w[S]);

				}

				dp[0][i][j] = g[0]; dp[1][i][j] = g[1];

			}

		}

	}

	ll ans = -1;

	for(int S = 0; S < (1 << (k - 1)); S ++)

		upd(ans, dp[S][1][n]);

	printf("%lld\n", ans);

	return 0;

}