Loj 3215 Muzyka pop

Posted on | Views:

数位 dp.

假定有一棵插入了 $[0,m]$ 内所有数的 01 Trie 树,我们可以在上面做简单的 dp 求出答案.

设 $f(x,l,r)$ 表示把 $[l,r]$ 内所有的 $b$ 都分配入 $x$ 的子树中能产生的最大贡献.

转移时枚举将 $[l,k]$ 内的 $b$ 分入 $x$ 左子树中, $[k+1,r]$ 内的 $b$ 分入 $x$ 右子树中.

$$
f(x,l,r) =\max_{l-1\le k\le r} f(x_{lson},l,k) + f(x_{rson},k+1,r)+\sum_{i=k+1}^r a_i
$$
但这棵 Trie 树的节点数目是 $O(m)$ 的,直接这样 dp 不可行.

注意到除去从 $m$ 到根这条链上的点,其它点的每个子树都是完全二叉树.

于是 dp 只需要记录当前节点深度,以及是否在从 $m$ 到根的链上.

其实这东西就是个数位 dp, 深度表示考虑到了哪一位,是否在链上表示是否顶住了上界.

用 Trie 树的形式可能比较容易理解贡献的计算.

时间复杂度 $O(n^3\log m)​$ .

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
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline ll read()
{
	ll out = 0, fh = 1;
	char jp = getchar();
	while ((jp > '9' || jp < '0') && jp != '-')
		jp = getchar();
	if (jp == '-')
		fh = -1, jp = getchar();
	while (jp >= '0' && jp <= '9')
		out = out * 10 + jp - '0', jp = getchar();
	return out * fh;
}
void print(ll x)
{
	if (x >= 10)
		print(x / 10);
	putchar('0' + x % 10);
}
void write(ll x, char c)
{
	if (x < 0)
		putchar('-'), x = -x;
	print(x);
	putchar(c);
}
const ll inf = 1e18;
const int K = 63, N = 200 + 10;
ll m, s[N], dp[K][2][N][N];
int n, k = 1;
int main()
{
	n = read(), m = read();
	while ((1LL << k) <= m)
		k++;
	for (int i = 1; i <= n; ++i)
		s[i] = s[i - 1] + read();
	for (int d = 0; d < k; ++d)
		for (int lim = 0; lim < 2; ++lim)
		{
			int t = lim && !(m >> d & 1LL);
			for (int l = 1; l <= n; ++l)
				for (int r = l; r <= n; ++r)
				{
					ll val = -inf;
					int mi = t ? r : l - 1;
					for (int k = mi; k <= r; ++k)
					{
						ll tmp = s[r] - s[k];
						if (d)
						{
							tmp += dp[d - 1][t][l][k];
							tmp += dp[d - 1][lim][k + 1][r];
						}
						else if (k - l + 1 > 1 || r - k > 1)
							continue;
						val = max(val, tmp);
					}
					dp[d][lim][l][r] = val;
				}
		}
	write(dp[k - 1][1][1][n], '\n');		
	return 0;
}