LibreOJ 6039 珠宝 | EarthMessenger 博客

题意

背包问题。给定一个正整数 $K$ ，和 $N$ 个二元组 $(C_i, V_i)$ ，表示每个物品的体积及价值。对于所有的 $1 \le i \le K$ ，求出当背包容积为 $K$ 时，最大的物品价值和。

$1 \le N \le 10^6$
$1 \le K \le 5 \times 10^4$
$1 \le C_i \le 300$
$0 \le V_i \le 10^9$

解析

容易注意到的一点是， $C$ 的值域非常小。考虑定义 $f_i(j)$ 表示考虑体积不超过 $i$ 的物品，背包体积为 $j$ 时的答案。令 $S_i(j)$ 表示所有体积为 $i$ 的物品的前 $j$ 大的和，体积相同的物品我们只需要考虑价值最大的几个就行了。容易写出转移方程：

f_i(j) = \max\limits_{0 \le k \le \frac{j}{k}} f_{i-1}(j-ik)+w_{i}(k)

从这个转移可以看出来，所有的 $f_i(j)$ 只和所有 $j \equiv k \pmod i$ 的 $f_i(k)$ 有关。按照余数分类，为了方便，令 $g_{i, r}(j) = f_i(ij + r)$ ，上面的转移方程可以写作：

\begin{aligned} g_{i, r}(j) &= \max\limits_{0 \le k < j} g_{i-1, r}(k) + w_{i}(j-k) \\ &= -\min\limits_{0 \le k < j} -g_{i-1, r}(k) - w_{i}(j-k) \end{aligned}

对于 $a \le b \le c \le d$ ，由于 $w$ 单调递增且增量不断减小，可以发现：

\begin{aligned} w(d-a)-w(c-a) &\le w(d-b)-w(c-b) \\ -w(c-a)-w(d-b) &\le -w(c-b)-w(d-a) \end{aligned}

即 $w$ 满足四边形不等式， $g$ 有决策单调性，可以用那种常见的分治优化。时间复杂度 $O(N \log N + 300 K \log K)$ 。

实现

const int MAXC = 300;

int main()
{
	std::ios::sync_with_stdio(false);
	std::cin.tie(nullptr);

	int n, k;
	std::cin >> n >> k;

	std::vector<std::vector<int>> a(MAXC + 1);
	for (int i = 0; i < n; i++) {
		int c, v;
		std::cin >> c >> v;
		a[c].emplace_back(v);
	}

	std::vector<long long> f(k + 1);
	for (int i = 1; i <= MAXC; i++) {
		std::sort(a[i].begin(), a[i].end(), std::greater<>());
		std::vector<long long> w(a[i].size() + 1);
		for (size_t j = 0; j < a[i].size(); j++) {
			w[j + 1] = w[j] + a[i][j];
		}

		int ws = w.size() - 1;
		auto g = f;
		std::fill(f.begin(), f.end(), 0);
		auto solve = [&w, ws, &g, &f, c = i](auto &&self, int q, int l, int r, int ll, int rr) -> void
		{
			int mid = l + (r - l) / 2;
			int p = ll;
			for (int i = ll; i < rr && i <= mid; i++) {
				if (g[p * c + q] + w[std::min(mid - p, ws)] <
				    g[i * c + q] + w[std::min(mid - i, ws)]) {
					p = i;
				}
			}
			f[mid * c + q] = g[p * c + q] + w[std::min(mid - p, ws)];
			if (l < mid) self(self, q, l, mid, ll, p + 1);
			if (mid + 1 < r) self(self, q, mid + 1, r, p, rr);
		};
		for (int j = 0; j < i; j++) {
			if (k - j < 0) continue;
			solve(solve, j, 0, (k - j) / i + 1, 0, (k - j) / i + 1); 
		}
	}

	for (int i = 1; i <= k; i++) {
		std::cout << f[i] << " ";
	}
	std::cout << std::endl;
}