题意描述
洛谷链接
约翰到商场购物，他的钱包里有 \(k (1 \le k
\le 16)\) 个硬币，面值的范围是 \(1 \sim
10^8\)。
约翰想按顺序买 \(n\) 个物品 \((1 \le n \le 10^5)\)，第 \(i\) 个物品需要花费 \(c_i\) 块钱，\((1
\le c_i \le 10^4)\)。
在依次进行的购买 \(n\)
个物品的过程中，约翰可以随时停下来付款，每次付款只用一个硬币，支付购买的内容是从上一次支付后开始到现在的这些所有物品（前提是该硬币足以支付这些物品的费用）。不幸的是，商场的收银机坏了，如果约翰支付的硬币面值大于所需的费用，他不会得到任何找零。
请计算出在购买完 \(n\)
个物品后，约翰最多剩下多少钱。如果无法完成购买，输出 \(-1\)。
解题思路
看到 \(k\)
的取值范围很容易想到使用状压。而对于使用硬币的每种状态，剩余钱财都是固定可计算的。于是我们可以设
\(f_i\) 为花费状态 \(i\)
的硬币时最多可购买的物品数。于是我们可得到下列转移方程（\(s_i\) 为购买前 \(i\) 个物品的所需花费，\(M\) 为所有硬币的集合）：
\[
f_i = \max\limits_{k \in m \wedge j = \complement_{i}\{k\}}
{\operatorname{fun}(k, f_j + 1)}
\]
其中 \(\operatorname{func}(i, j)\)
表示总共有 \(i\) 块钱时从第 \(j\)
个商品开始付款最多可购买到第几个商品。很显然 \(\operatorname{func}(i, j)\)
可使用二分求解。
最终对于所有 \(f_i = n\) 所对应的
\(i\)
状态，计算剩余钱的最大值即可。时间复杂度为 \(O(k 2^k \log n)\)。
代码演示
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| #include <cstdio>
#include <algorithm>
const int MAXK = 16;
const int MAXN = 100000;
int main() {
int k, n;
scanf("%d %d", &k, &n);
static long long money[MAXK];
for (int i = 0; i < k; i++) scanf("%lld", &money[i]);
static long long s[MAXN + 1];
for (int i = 1; i <= n; i++) {
scanf("%lld", &s[i]);
s[i] += s[i - 1];
}
static int f[1 << MAXK];
for (int i = 1; i < (1 << k); i++) {
for (int j = 0; j < k; j++) {
if ((i >> j) & 1) {
int x = i ^ (1 << j);
if (f[x] == n) {
f[i] = n;
continue;
}
int l = f[x] + 1, r = n;
while (l < r) {
int mid = (l + r + 1) / 2;
if (s[mid] - s[f[x]] <= money[j]) l = mid;
else r = mid - 1;
}
f[i] = std::max(f[i], l);
}
}
}
long long ans = -1;
for (int i = 1; i < (1 << k); i++) {
if (f[i] == n) {
long long res = 0;
for (int j = 0; j < k; j++) if (!((i >> j) & 1)) res += money[j];
ans = std::max(ans, res);
}
}
printf("%lld\n", ans);
return 0;
}
|