Loj 6039 珠宝

Posted on | Views:

决策单调性优化 dp.

题意就是要求解一个 01 背包,但通常的 $O(nm)$ 的 dp 会超时.

注意到每种物品的体积不会超过 $300$ ,可以考虑设计与它相关的状态进行 dp .

设 $val(i,j)$ 表示选 $j$ 件体积为 $i$ 的物品能获得的最大收益.

设 $f(i,j)$ 表示考虑了所有体积 $\le i$ 的物品,花费了 $j$ 万元能获得的最大收益.

转移时枚举体积为 $i$ 的物品选了 $k$ 个,
$$
f(i,j)=\max_{k} \lbrace f(i-1,j-i\times k)+val(i,k) \rbrace
$$
注意到 $val(i,j)-val(i,j-1)$ 就是体积为 $i$ 的物品中,第 $j$ 大的收益,所以这个差值是不增的,即 $val(i)$ 是凸的.

于是我们把所有 $j$ 按照模 $i$ 分类,每一类内部具有决策单调性,可以用分治优化.

时间复杂度 $O(n\log n+\max C\cdot m\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
68
69
70
71
72
73
74
75
//%std
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
inline int read()
{
	int 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;
}
const int K = 300 + 10, N = 5e4 + 10;
vector<ll> val[K];
int n, m, siz[K];
ll f[2][N], g[2][N];
void solve(int id, int i, int l, int r, int kl, int kr)
{
	int mid = (l + r) >> 1, pk = kl;
	ll res = 0;
	for (int k = kl; k <= mid && k <= kr; ++k)
	{
		ll tmp = g[id ^ 1][k] + val[i][min(mid - k, siz[i] - 1)];
		if (tmp > res)
			res = tmp, pk = k; 
	}
	g[id][mid] = res;
	if (l <= mid - 1)
		solve(id, i, l, mid - 1, kl, pk);
	if (mid + 1 <= r)
		solve(id, i, mid + 1, r, pk, kr);
}
int main()
{
	n = read(), m = read();
	int mx = 0;
	for (int i = 1; i <= n; ++i)
	{
		int c = read(), v = read();
		val[c].push_back(v);
		mx = max(mx, c);
	}
	for (int i = 1; i <= mx; ++i)
	{
		sort(val[i].begin(), val[i].end());
		val[i].push_back(0);
		reverse(val[i].begin(), val[i].end());
		siz[i] = val[i].size();
		for (int j = 1; j < siz[i]; ++j)
			val[i][j] += val[i][j - 1];
	}
	int id = 0;
	for (int i = 1; i <= mx; ++i)
		if (siz[i] != 1)
		{
			id ^= 1;
			for (int j = 0, u = 0; j < i; ++j, u = 0)
			{
				for (int v = j; v <= m; ++u, v += i)
					g[id ^ 1][u] = f[id ^ 1][v];
				solve(id, i, 0, u - 1, 0, u - 1);
				u = 0;
				for (int v = j; v <= m; ++u, v += i)
					f[id][v] = g[id][u];
			}
		}
	for (int i = 1; i <= m; ++i)
		printf("%lld ", f[id][i]);
	puts("");
	return 0;
}