HD玩具 - 背包

HD玩具

原文链接

https://blog.lucien.ink/archives/455/

题目地址

http://icpc.upc.edu.cn/problem.php?id=12163

题目

商店正在出售小C最喜欢的系列玩具,在接下来的n周中,每周会出售其中的一款,同一款玩具不会重复出现。
由于是小C最喜欢的系列,他希望尽可能多地购买这些玩具,但是同一款玩具小C只会购买一个。同时,小C的预算只有m元,因此他无法将每一款都纳入囊中。此外,小C不能连续两周都购买玩具,否则他会陷入愧疚。现在小C想知道,他最多可以买多少款不同的玩具呢?

题解

$f[i][j]$ 代表第 $i$ 天有 $j$ 元的时候最多可以买多少个,可以比较容易得出转移方程:

$$f[i][j] = max(f[i - 2][j - cost[i]] + 1, f[i - 1][j])$$

需要注意的是,如果买不起($j < cost[i]$)的话,有:

$$f[i][j] = f[i - 1][j]$$

$i$ 对应的那一维可以用滚动数组优化,整体时间复杂度为 $O(NM)$ ,空间复杂度为 $O(M)$ 。

实现

#include <bits/stdc++.h>
const int maxm = int(5e4) + 7;
int n, m, f[2][maxm];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1, cost, cur, pre; i <= n; i++) {
        scanf("%d", &cost);
        cur = i & 1, pre = cur ^ 1;
        for (int j = m; j >= 0; j--) {
            if (j >= cost) f[cur][j] = std::max(f[cur][j], f[cur][j - cost] + 1);
            f[cur][j] = std::max(f[cur][j], f[pre][j]);
        }
    }
    printf("%d\n", f[n & 1][m]);
    return 0;
}
最后修改:2019 年 07 月 13 日 08 : 50 AM
谢谢老板!

发表评论