LibreOJ 6039 珠宝

标签: lojdpknapsack

题意

背包问题。给定一个正整数 ,和 个二元组 ,表示每个物品的体积及价值。对于所有的 ,求出当背包容积为 时,最大的物品价值和。

解析

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

从这个转移可以看出来,所有的 只和所有 有关。按照余数分类,为了方便,令 ,上面的转移方程可以写作:

对于 ,由于 单调递增且增量不断减小,可以发现:

满足四边形不等式, 有决策单调性,可以用那种常见的分治优化。时间复杂度

实现

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;
}