给定 \(n\) 个物品，第 \(i\) 个物品有体积 \(c_i\)，价值 \(v_i\)。给定 \(K\)，对 \(1 \sim K\) 的所有 \(i\) 求大小为 \(i\) 的背包的最大价值。
\(n \leq 10^6\)，\(K \leq 5 \times 10^4\)，\(c_i \leq 300\)，\(0 \leq v_i \leq 10^9\)，时限 \(\text{2.0s}\)。
注意到 \(c_i\) 范围很小，考虑往 \(\mathcal{O}(CK)\) 之类的东西上靠一靠。我们把 \(c_i\) 相同的物品放在一起并按 \(v_i\) 排序，那么取的一定是一段前缀。更进一步地，设 \(g_i\) 为 \(c_k = i\) 的物品对应的结果，即 \(g_{i,j}\) 为取 \(j\) 个体积为 \(i\) 的物品的最大价值，那么 \(g_i\) 是凸的。
所以我们就搞出了 \(\mathcal{O}(C)\) 个凸包，很乱斗。考虑每次怎么把一个凸包合并到答案上，假设枚举了当前的体积 \(c\)，那么答案数组中下标 \(\bmod c\) 不同的位置互不干扰，可以独立做。对每个同余类拉出来之后 DP 大概长成 \(f_i \gets f_j + g_{c,i-j}\) 这个样子，由于 \(g_c\) 上凸并且单调不降，因此它满足四边形不等式，于是有决策单调性，分治即可做到 \(\mathcal{O}(CK\log K)\)。
code
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef vector <LL> vi;
constexpr int M = 3e2 + 5, K = 5e4 + 5, N = 1e6 + 5;
int n, k, C;
vi f[M], ans, p, q, tmp; int L[M];
void trans(int l, int r, int ql, int qr) {
if (l > r) return;
int m = l + r >> 1;
LL mx = 0, pos = 0;
int rb = min(qr, m);
for (int i = ql; i <= rb; i++) {
LL val = 0;
if (m - i >= q.size()) val = q.back();
else val = q[m - i];
if (p[i] + val > mx) mx = p[i] + val, pos = i;
}
tmp[m] = mx;
trans(l, m - 1, ql, pos);
trans(m + 1, r, pos, qr);
}
int main() {
ios :: sync_with_stdio(false);
cin.tie(nullptr);
freopen("jewelry.in", "r", stdin);
freopen("jewelry.out", "w", stdout);
cin >> n >> k;
for (int i = 1, c, v; i <= n; i++) {
cin >> c >> v;
f[c].push_back(v);
L[c]++;
C = max(C, c);
}
for (int i = 1; i <= C; i++) {
f[i].push_back(0);
sort(f[i].begin(), f[i].end()), reverse(f[i].begin(), f[i].end());
for (int j = 1; j < f[i].size(); j++) {
f[i][j] = f[i][j] + f[i][j - 1];
}
for (int j = f[i].size() - 1; j >= 1; j--) f[i][j] = f[i][j - 1];
f[i][0] = 0;
while (L[i] > K) f[i].pop_back(), L[i]--;
}
ans.resize(k + 1);
tmp.resize(k + 1);
for (int c = 1; c <= C; c++) {
q.clear();
for (int i = 0; i <= L[c]; i++) q.push_back(f[c][i]);
for (int i = 1; i <= c; i++) {
p.clear();
int j = i;
if (i == c) p.push_back(0);
while (j <= k) p.push_back(ans[j]), j += c;
trans(0, p.size() - 1, 0, p.size() - 1);
j = i;
int o = 0;
if (i == c) o = 1;
while (j <= k) ans[j] = tmp[o], j += c, o++;
}
for (int i = 1; i <= k; i++) ans[i] = max(ans[i], ans[i - 1]);
}
for (int i = 1; i <= k; i++) cout << ans[i] << " \n"[i == k];
return 0;
}
/*
5 10
3 2
1 48
3 25
2 76
4 83
*/