[HAOI2016]字符合并

题目描述

题目传送门

思路

假设 $dp_{l,r,S}$ 表示区间 $[l,r]$ 合并成二进制数 $S$ 的最大分数。

然后考虑转移。

首先有一个结论，尽可能多的合并直到不能合并位置。这样我们可以考虑合并后长度为 $1$ 的区间。显然，这个区间的大小为集合 $S =\{x|n \in \mathbb{N}\ x=nk-n+1\}$，然后就有 $dp_{l,r,2w}=dp_{l,mid,w}+dp_{mid+1,r,0}$，其中 $r - mid \in S$；以及 $dp_{l,r,2w+1}=dp_{l,mid,w} + dp_{mid+1,r,1}$，其中 $r-mid\in S$。

然后就是初始化，$i$ 到 $j$ 恰好有 $k$ 位数字，我们直接把它合并一次，具体实现看代码。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int MAXK = 8, MAXN = 310;

int N, K;
int A[MAXN], W[MAXN], C[MAXN];
int Dp[MAXN][MAXN][1 << MAXK];

signed main() {
	memset(Dp, 0xcf, sizeof Dp);
	cin >> N >> K;
	for (int i = 1; i <= N; i++) cin >> A[i];
	for (int i = 0; i < (1 << K); i++)
		cin >> C[i] >> W[i];
	for (int i = 1; i <= N; i++) 
		Dp[i][i][A[i]] = 0;
	for (int len = 2; len <= N; len++) {
		for (int l = 1; l + len - 1 <= N; l++) {
			int r = l + len - 1;
			int tmp = (len - 1) % (K - 1);
			if (!tmp) tmp = K - 1;
			for (int k = r - 1; k >= l; k -= (K - 1)) {
				for (int w = 0; w < (1 << tmp); w++) {
					Dp[l][r][w << 1] = max(Dp[l][r][w << 1], Dp[l][k][w] + Dp[k + 1][r][0]);
					Dp[l][r][w << 1 | 1] = max(Dp[l][r][w << 1 | 1], Dp[l][k][w] + Dp[k + 1][r][1]);
				}
			}
			if (tmp == K - 1) {
				int CYB1 = INT_MIN, CYB2 = INT_MIN;

                for (int k = 0; k < (1 << K); ++ k) {
                    if (C[k] == 0)
                        CYB1 = max(CYB1, Dp[l][r][k] + W[k]);
                    else
                        CYB2 = max(CYB2, Dp[l][r][k] + W[k]);
                }

                Dp[l][r][0] = CYB1;
				Dp[l][r][1] = CYB2;
			}
		}
	}
	
	int Ans = INT_MIN;
	for (int i = 0; i < (1 << K); i++)
		Ans = max(Ans, Dp[1][N][i]);	
	cout << Ans << endl;
	return 0;
}