题目描述

$01$ 背包，数据范围 $1 \le n \le 1e06, 1 \le weight_i \le 300$

题解

神仙 $01$ 背包

考虑重量较小，故可以考虑根据重量分层处理

令 $f_{i, j}$ 表示使用前 $i$ 个重量，总共花费 $j$ 容量的最大价值

容易注意到在同一重量中显然要优先选择价值大的，故将每种重量按价值排序，令 $sumv_{i, j}$ 表示重量为 $i$ 的前 $j$ 大的价值前缀和，则有
$$
f_{i, j} = \max\limits_k \{f_{i - 1, j - ki} + sumv_{i, k}\}
$$
然后（通过看题解）可以发现，因为是 $j - ki$，故可以考虑按照 $j \mod i$ 分类处理，这样是满足决策单调性的

至于证明，为了方便可以将式子简化成 $f_i = \max \{f_j +sumv_{i - j}\}$ 的形式，然后用反证法或是四边形不等式都容易证明

那么最后就可以用决策单调性的套路代码或者是用分治解决了

分治比较简单，大概就是看在处理区间 $[u, v]$， $[l, r]$ 决策区间内对于 $mid$ 位置在 $[l, r]$ 中最有决策在哪个位置，然后左右递归即可

代码

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
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;

typedef long long LL;

const int MAXK = 5e04 + 10;
const int MAXC = 300 + 10;

int N, K, C = 0;
vector<int> value[MAXC];
vector<LL> prefix[MAXC];

bool comp (const int& a, const int& b) {
	return a > b;
}

LL f[MAXC][MAXK]= {0};
LL trans[MAXK]= {0};
LL w (int i, int j, int s) {
	int p = (i - j) / s;
	if (p >= (int) prefix[s].size())
		return - 1ll;
	return f[s - 1][j] + prefix[s][p];
}
void solve (int p, int u, int v, int l, int r) { // 层数 处理区间 决策区间
	int mid = (u + v) >> 1;
	LL maxi = - 1, posi = 0;
	for (int i = l; i <= min (mid, r); i ++) {
		LL cont = w (trans[mid], trans[i], p);
		if (cont > maxi)
			maxi = cont, posi = i;
	}
	if (u == v) {
		f[p][trans[u]] = maxi;
		return ;
	}
	solve (p, u, mid, l, posi);
	solve (p, mid + 1, v, posi, r);
}

int getnum () {
	int num = 0;
	char ch = getchar ();

	while (! isdigit (ch))
		ch = getchar ();
	while (isdigit (ch))
		num = (num << 3) + (num << 1) + ch - '0', ch = getchar ();

	return num;
}
void write (LL x) {
	if (x >= 10)
		write (x / 10);
	putchar (x % 10 + '0');
}

int main () {
	N = getnum (), K = getnum ();
	for (int i = 1; i <= N; i ++) {
		int c = getnum (), v = getnum ();
		C = max (C, c), value[c].push_back(v);
	}
	for (int i = 1; i <= C; i ++) {
		sort (value[i].begin(), value[i].end(), comp);
		LL sum = 0;
		prefix[i].push_back(sum);
		for (int j = 0; j < (int) value[i].size(); j ++)
			sum += value[i][j], prefix[i].push_back(sum);
		for (int j = 0; j < i; j ++) {
			int limit;
			trans[limit = 1] = j;
			while (trans[limit] + i <= K)
				limit ++, trans[limit] = trans[limit - 1] + i;
			solve (i, 1, limit, 1, limit);
		}
	}
	for (int i = 1; i <= K; i ++) {
		if (i > 1)
			putchar (' ');
		write (f[C][i]);
	}
	puts ("");

	return 0;
}

/*
5 10
3 2
1 48
3 25
2 76
4 83
*/