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