P5985 [PA2019] Muzyka pop 题解

是蛮有意思的一道题。

\(n\le 200\)，第一感觉是区间 dp，但是又不好设出状态。考虑 \(b\) 单调递增的过程中的性质，考虑后得到 \(b\) 的最高含 \(1\) 的位一定是单调不降的，于是我们考虑将最高的含 \(1\) 的位设入状态。

第一反应是设 \(f_{i,j}\) 表示选了前 \(i\) 个 \(a\)，最高位 \(\le j\) 的最大值。设 \(s(l,r,i)\) 表示 \([l,r]\) 区间最高位都是 \(i\) 的方案数，则 \(f_{i,j}=\max\{f_{k,j-1}+s(k+1,i,j)\}\)。考虑 \(s(l,r,i)\) 的含义是确定了最高位，其它位不关心，于是 \(s(l,r,i)\) 实际上是 \([l,r]\) 区间最高位 \(\le j\) 的最大值 \(+\sum_{l}^r a_i\)。

于是区间 dp 的定义式便容易得出：\(f_{i,l,r}\) 表示最高位 \(\le i\)，选择 \([l,r]\) 的最大值。转移的式子是 \(f_{i,l,r}=\max\{f_{i-1,l,k}+f_{i-1,k+1,r}+\sum_{l}^r a_i \}\)。现在考虑加上 \(m\) 限制的情况。

依据常见的套路，我们再定义 \(g_{i,l,r}\) 表示最高位的赋值和 \(m\) 在这一位上的取值相同时的最大值。那么当 \(m\) 这一位为 \(0\) 时，\(g_{i,l,r}=g_{i-1,l,r}\)。否则 \(g_{i,l,r}=\max\{f_{i-1,l,k}+g_{i-1,k+1,r}+\sum_l^r a_i \}\)。

需要注意的是这样 dp 无法处理一位上只取一个数的情形。套路地，我们预处理 \(f_{0,i,i-1}=g_{0,i,i-1}=0\)，然后将 \(k\) 的范围改为枚举 \(k\in[l-1,r]\) 即可。

本题的关键是能将 最高的含 \(1\) 的位 设入状态，得出区间 dp 的套路，并得出 \(g\) 的转移定义。

代码：

#include <bits/stdc++.h>
#define int long long
#define N 205
using namespace std;
int n, m;
int a[N], sum[N];
int f[66][N][N], g[66][N][N];
signed main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
		scanf("%lld", &a[i]), sum[i] = sum[i - 1] + a[i];
	memset(f, -0x3f, sizeof f);
	memset(g, -0x3f, sizeof g);
	for (int i = 1; i <= n; i++) 
		f[0][i][i] = g[0][i][i] = 0;	
	int M = ceil(log2(m)) + 1;
	for (int i = 0; i <= M; i++)
		for (int j = 1; j <= n + 1; j++)
			f[i][j][j - 1] = g[i][j][j - 1] = 0;
	for (int i = 1; i <= M; i++)
		for (int l = 1; l <= n; l++)
			for (int r = l; r <= n; r++) {
				for (int k = l - 1; k <= r; k++)
					f[i][l][r] = max(f[i][l][r], f[i - 1][l][k] + f[i - 1][k + 1][r] + sum[r] - sum[k]);
				g[i][l][r] = max(g[i][l][r], g[i - 1][l][r]);
				if (!((m >> (i - 1)) & 1))
					continue;
				for (int k = l - 1; k <= r; k++)
					g[i][l][r] = max(g[i][l][r], f[i - 1][l][k] + g[i - 1][k + 1][r] + sum[r] - sum[k]);
			}
	cout << g[M][1][n] << "\n";
	return 0;
}