AcWing 1022. 宠物小精灵之收服

题目传送门

一、题目解析

题目描述
傻东西 和 皮神 一起去抓 宝可梦

一共会遇到 \(n\) 个 野生宝可梦，小智有 \(m\) 个 精灵球，皮神有 \(t\) 滴 血

对于每个 野生宝可梦 来说，如果要捕捉他，需要 \(v_{1i}\) 个 精灵球，战斗后皮神要掉 \(v_{2i}\) 滴 血

如果皮神 血量 \(≤0\)，则小智停止狩猎

小智对于每个 野生宝可梦 要么收服，要么逃跑

求一种方案：收服 尽可能多 的 野生宝可梦 ；如果收服数量一样，要皮神 血量最多

输出该方案的 野生宝可梦 收服数量，以及皮神战斗结束后的 剩余血量

分析

y总在标签里很贴心的贴了一个** 阅读理解** 的tag，没错这就是一道阅读理解题

本题是一道 01背包 的扩展题 —— 二维费用01背包问题

把 野生宝可梦 看做物品，则捕捉他需要的 精灵球 个数就是第一费用，战斗皮神要掉的血就是第二费用

最后答案要求物品数量最多，因此我们可以用状态的属性来表示选择的物品数

以上就是本题的** 阅读理解分析部分** ，接下来直接上闫氏DP分析法

闫氏DP分析法

初始状态：f[0][0][0]
目标状态：f[n][m][t - 1] （皮神不能 再起不能 才算抓住那个 宝可梦 ）

二、实现代码

时间复杂度：\(O(n×m×k)\)

#include <bits/stdc++.h>

using namespace std;

const int N = 110;  //野生小精灵的数量
const int M = 1010; //小智的精灵球数量
const int K = 510;  //皮卡丘初始的体力值

int n, m, t;
int v1[N], v2[N];

int f[M][K];//一维：精灵球数量，二维：皮卡丘的体力值

int main() {
    //input
    cin >> m >> t >> n;
    //收服该小精灵需要的精灵球的数量，以及收服过程中对皮卡丘造成的伤害
    for (int i = 1; i <= n; i++) cin >> v1[i] >> v2[i];

    //dp
    //多维费用01背包
    //降维需要将体积1、体积2倒序枚举
    //注意血不能全用了，需要留一个点
    for (int i = 1; i <= n; i++)
        for (int j = m; j >= v1[i]; j--)
            for (int k = t - 1; k >= v2[i]; k--)
                f[j][k] = max(f[j][k], f[j - v1[i]][k - v2[i]] + 1);

    //最多收服多少个小精灵
    cout << f[m][t - 1] << " ";
    //找到满足最大价值的所有状态里，第二维费用消耗最少的
    int cost = t - 1;
    for (int k = 0; k <= t - 1; k++)
        if (f[m][k] == f[m][t - 1]) cost = min(cost, k);

    //收服最多个小精灵时皮卡丘的剩余体力值最大是多少
    cout << t - cost << endl;
    return 0;
}