0%

[EZEC - 1] 出题

题目

题目链接

题目大意:给出 $n$ 个物品,每个物品有一个价值 $v$ 和空间 $m$,有 $k$ 次机会可以将当前物品的价值翻一倍,每种物品只能进行一次这样的操作,物品最多选 $n - 1$ 个,求最大价值。$1 \le n \le 100, 0 \le m \le 1000$。

思路

其实不难发现,题目中的 “有一个物品不能取” 这句话其实是废话,因为一般来说背包问题不能全部取完,不取那个不在最终状态里的物品就行了。

这道题无非就是又加了一维的情况。

设 $f(i, j)$ 表示体积为 $i$,用了 $j$ 次翻倍时的最大收益。则状态转移方程为 $f(i, j) = \max(f(i - m_k, j) + v_k, f(i - m_k, j - 1) + 2v_k)$。

注意到每个老师只能用一次,所以枚举 $j$ 时要注意一下范围。

然后别忘了我们最开始说的那种情况,如果所有物品都能取,那就是一个简单的贪心,注意特判一下。

代码

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

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

int f[1010][1010];
int a[1010], x[1010];
int n, m, ans, t, s;

int main() {
read(n), read(m), read(t);
for (int i = 1; i <= n; ++i) read(a[i]), read(x[i]), s += x[i];
if (s <= m) {
std::sort(a + 1, a + n + 1, [](int a, int b) {
return a > b;
} );
for (int i = 1; i <= t; ++i) ans += a[i] * 2;
for (int i = t + 1; i < n; ++i) ans += a[i];
printf("%d\n", ans);
return 0;
}
for (int i = 1; i <= n; ++i) {
for (int j = m; j >= x[i]; --j) {
f[j][0] = std::max(f[j][0], f[j - x[i]][0] + a[i]);
ans = std::max(ans, f[j][0]);
for (int k = 1; k <= std::min(t, i); ++k) {
f[j][k] = std::max(f[j][k], std::max(f[j - x[i]][k] + a[i], f[j - x[i]][k - 1] + a[i] * 2));
ans = std::max(ans, f[j][k]);
}
}
}
printf("%d\n", ans);
return 0;
}