LibreOJ 6039 珠寶

題意

背包問題。給定一個正整數 $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;
}