0%

[SNOI2017] 英雄联盟

题目

题目链接

题目大意:有 $n$ 个物品,每个物品的种类有 $k$ 种,价格为 $c$。设 $x$ 为每种物品买到的种类的乘积,求当 $x \ge m$ 时的最少花费。$M \le 10^{17}, 1 \le k \le 10, 1 \le c \le 199, n \le \max(5, \log_2^4 10)$。

思路

这个 $n$ 还要算一下是我没想到的,算出来大概是 $120$ 左右的样子。

由于 $k, c$ 都十分小,可以求出一个把所有物品都买下来需要的花费,把这个当成背包的体积。

然后做多重背包,这里 $k$ 很小,并不用做其他的优化。

最后判断一下即可。

注意初始化 f[0] = 1

代码

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
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

template <class T>
inline void read(T &x) {
x = 0;
int f = 0;
char ch = getchar();
while (!isdigit(ch)) { f |= ch == '-'; ch = getchar(); }
while (isdigit(ch)) { x = (x << 1) + (x << 3) + (ch ^ 48); ch = getchar(); }
x = f ? -x : x;
return ;
}

typedef long long LL;

LL k[260], q[260], f[510000];
LL n, m, M;

int main() {
read(n), read(m);
for (int i = 1; i <= n; ++i) read(k[i]);
for (int i = 1; i <= n; ++i) read(q[i]), M += q[i] * k[i];
f[0] = 1;
for (int i = 1; i <= n; ++i) {
for (int j = M; j >= 0; --j) {
for (int l = 0; l <= k[i] && l * q[i] <= j; ++l) {
f[j] = std::max(f[j], f[j - l * q[i]] * l);
}
}
}
for (int i = 0; i <= M; ++i) {
if (f[i] >= m) {
printf("%d\n", i);
return 0;
}
}
return 0;
}