P1782 旅行商的背包 Solution

Description

有一个体积为 $C$ 的背包和若干种物品.
前 $n$ 种物品，第 $i$ 种体积为 $v_i$，价值 $w_i$，有 $d_i$ 件.
后 $m$ 种物品，每种对应一个函数 $f(x)=a_i{x}^2+b_{i}x+c_i$，表示若选 $x$ 体积的这件物品，价值为 $f(x)$.（不选当作选 $0$ 体积）
选择一些物品，使得体积和不超过 $C$，求最大价值.

Limitations

$1\le n\le 10^4$
$1\le m\le 5$
$1\le C\le 10^4$
$1\le w_i,v_i,d_i\le 1000$
$|a_i|,|b_i|,|c_i|\le 1000$
$1\text{s},128\text{MB}$

Solution

不考虑后 $m$ 件物品，那么就是一个多重背包，然而暴力跑 DP 铁定超时，需要优化.
多重背包一般有两种优化方式：二进制拆分和单调队列.
由于常数原因，我们选用二进制拆分，将每堆物品分成若干组，每组分别有 $2^0,2^1,\cdots ,2^{k-1},d-2^k+1$ 个（$k$ 是满足 $n-2^k+1>0$ 的最大整数）.
那么用这些组就可以组出 $0\sim d$ 个的所有选法，这样就转化成了 $01$ 背包.

对于后 $m$ 个物品，由于 $m$ 很小，我们可以枚举给每个物品分配的体积，暴力更新.

总时间复杂度为 $O(C\sum \log d_i+m{C}^2)$.

Code

$1.15\text{KB},1.83\text{s},2.55\text{MB}\text{(in total, C++20 with O2)}$

#include <bits/stdc++.h>
using namespace std;

using i64 = long long;
using ui64 = unsigned long long;
using i128 = __int128;
using ui128 = unsigned __int128;
using f4 = float;
using f8 = double;
using f16 = long double;

template<class T>
bool chmax(T &a, const T &b){
	if(a < b){ a = b; return true; }
	return false;
}

template<class T>
bool chmin(T &a, const T &b){
	if(a > b){ a = b; return true; }
	return false;
}


signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	
	int n, m, c;
	scanf("%d %d %d", &n, &m, &c);
	
	vector<pair<int, i64>> goods;
	for (int i = 0, v, w, d; i < n; i++) {
		scanf("%d %d %d", &v, &w, &d);
		int t = 1;
		while (d) {
			if (d - t <= 0) t = d, d = 0;
			else d -= t;
			goods.emplace_back(t * v, 1LL * t * w);
			t <<= 1;
		}
	}
	
	vector<i64> dp(c + 1);
	for (auto [v, w] : goods) 
	    for (int k = c; k >= v; k--) chmax(dp[k], dp[k - v] + w);
	
	for (int i = 0, A, B, C; i < m; i++) {
		scanf("%d %d %d", &A, &B, &C);
		auto f = [&](int x) { return 1LL * A * x * x + 1LL * B * x + C; };
		for (int k = c; k >= 0; k--)
		    for (int j = 0; j <= k; j++) chmax(dp[k], dp[k - j] + f(j));
	}
	printf("%lld", dp[c]);
	return 0;
}