Fate

最近xhd正在玩一款叫做FATE的游戏，为了得到极品装备，xhd在不停的杀怪做任务。久而久之xhd开始对杀怪产生的厌恶感，但又不得不通过杀怪来升完这最后一级。现在的问题是，xhd升掉最后一级还需n的经验值，xhd还留有m的忍耐度，每杀一个怪xhd会得到相应的经验，并减掉相应的忍耐度。当忍耐度降到0或者0以下时，xhd就不会玩这游戏。xhd还说了他最多只杀s只怪。请问他能升掉这最后一级吗？

输入格式:

输入数据有多组，对于每组数据第一行输入n，m，k，s(0 < n,m,k,s < 100)四个正整数。分别表示还需的经验值，保留的忍耐度，怪的种数和最多的杀怪数。接下来输入k行数据。每行数据输入两个正整数a，b(0 < a,b < 20)；分别表示杀掉一只这种怪xhd会得到的经验值和会减掉的忍耐度。(每种怪都有无数个)

输出格式:

输出升完这级还能保留的最大忍耐度，如果无法升完这级输出-1。

输入样例:

10 10 1 10
1 1
10 10 1 9
1 1
9 10 2 10
1 1
2 2

输出样例:

0
-1
1

我的题解：

#include <iostream>
#include <vector>
using namespace std;

int solve(int n, int m, int k, int s, vector<pair<int, int>>& monsters) {
    //分别表示还需的经验值n，保留的忍耐度m，怪的种数k和最多的杀怪数s
    vector dp(n + 1, vector(s + 1, -1000));//还需的经验值，杀怪数，剩余的忍耐度，-1000代表不存在
    dp[n][0] = m;//刚开始，还差n经验，忍耐度为m

    for (int i = 0; i < k; ++i) {//遍历所有的怪
        int exp = monsters[i].first, cost = monsters[i].second;
        for (int j = 0; j < s; ++j) {//杀j只它，剩余的忍耐度
            for (int cur_exp = 0; cur_exp <= n; ++cur_exp) {//为什么从前往后？因为后面的需要用到前面的经验。
                if (dp[cur_exp][j] >= 0) {//忍耐度存在
                    int next_exp = max(0, cur_exp - exp);//推导杀一只怪之后的经验，最小为0
                    dp[next_exp][j + 1] = max(dp[next_exp][j + 1], dp[cur_exp][j] - cost);//更新杀一只怪后忍耐度，选忍耐度最多的。
                }
            }
        }
    }

    int result = -1;
    for (int j = 0; j <= s; ++j) {
        if (dp[0][j] >= 0) {//经验到达，忍耐度存在
            result = max(result, dp[0][j]);//找到最大的那个
        }
    }
    return result;
}

int main() {
    int n, m, k, s;
    while (cin >> n >> m >> k >> s) {
        vector<pair<int, int>> monsters(k);
        for (int i = 0; i < k; ++i) {
            cin >> monsters[i].first >> monsters[i].second;
        }

        int result = solve(n, m, k, s, monsters);//保留的忍耐度
        if (result >= 0) {
            cout << result << endl;
        } else {
            cout << "-1" << endl;
        }
    }
    return 0;
}

思考：

问题背景

  • 你需要获得一定的经验值（n）。
  • 你有一定的忍耐度（m），每次杀怪都会消耗一部分。
  • 怪物有多种（k种），每种怪物提供不同的经验值和消耗不同的忍耐度。
  • 你最多可以杀s个怪物。

此处我们会发现问题的约束有点多，一维数组已经满足不了我们。

动态规划的思路

  1. 定义状态: dp[i][j]表示你还需要i点经验，且杀了j个怪物时的剩余最大忍耐度。
  2. 初始化状态: 初始时，你需要n点经验，且未杀任何怪物，因此dp[n][0] = m。
  3. 状态转移:
    • 遍历每一种怪物。
    • 对于每种怪物，尝试杀0到s-1个，查看不同数量下的剩余忍耐度和所需经验。
    • 对每个杀怪数量，检查如果杀了这个怪物后，是否能得到更好的剩余忍耐度（即dp[next_exp][j+1]）。
    • 转移方程：如果杀死一个怪物后剩余忍耐度更高，则更新dp[next_exp][j+1]。
  4. 寻找结果: 在所有经验值为0（即达到目标经验值）的情况中，找到忍耐度最大的那个。

首先看main函数，这是我们解题的主要步骤：

vector<pair<int, int>> monsters(k);

创建一个mosters数对，代表怪物的种类存储结构。有k种怪兽，而每种怪兽会给出两个正整数a，b(0 < a,b < 20)；分别表示杀掉一只这种怪会得到的==经验值==和==会减掉的忍耐度==。注意此处，我们最终的忍耐度是看剩余的忍耐度，而经验值是看总共的经验值，一个是消耗，一个是增加，而目标是得到忍耐度的最大值。那么我们首先会想到尽量少减掉忍耐度，尽量增加更多的经验。


if (result >= 0) {
            cout << result << endl;
        } else {
            cout << "-1" << endl;
        }

这里也很简单。调用一个函数获得忍耐度的最大值，如果不存在，将会返回负值；如果存在，输出即可。




接下来看到solve函数，真正的逻辑核心。

int solve(int n, int m, int k, int s, vector<pair<int, int>>& monsters)

数组我们一般引用它地址

vector dp(n + 1, vector(s + 1, -1000));//还需的经验值，杀怪数，剩余的忍耐度，-1000代表不存在
    dp[n][0] = m;//刚开始，还差n经验，忍耐度为m

初始化的时候记得设置动态规划的数组，其值是目标结果，而初始状态需要赋有意义的值。

int exp = monsters[i].first, cost = monsters[i].second;

采用first和second代替a和b，方便自己思考记住。这个看个人习惯，就是说我们不需要增加设置数据结构的环节，其实是这样。

for (int i = 0; i < k; ++i) {//遍历所有的怪
    int exp = monsters[i].first, cost = monsters[i].second;
    for (int j = 0; j < s; ++j) {//杀j只它，剩余的忍耐度
        for (int cur_exp = 0; cur_exp <= n; ++cur_exp) {//为什么从前往后？因为后面的需要用到前面的经验。
            if (dp[cur_exp][j] >= 0) {//忍耐度存在
                int next_exp = max(0, cur_exp - exp);//推导杀一只怪之后的经验，最小为0
                dp[next_exp][j + 1] = max(dp[next_exp][j + 1], dp[cur_exp][j] - cost);//更新杀一只怪后忍耐度，选忍耐度最多的。
            }
        }
    }
}

最后解释真正重要的部分。

我们外层遍历所有种类的怪，而内遍历杀所有个数，就可以考虑到所有种类，每种个数杀任意只得所有情况了，而实际得到的dp值是可以实时更新的。

最里面一层for，注释里已经解释了exp为什么从前往后遍历，我们可以自己验证一下，假设第一只怪数值是(1,1)，第一次遍历的时候发现dp[n][0]处有一个m，那么我们考虑next_exp就是m-1，dp[n-1][1]表示杀了一只怪之后还差n-1点经验，即增加了一点经验，之后的忍耐值。可想而知，它是下降的，那么我们比较杀了这只怪之后的忍耐度会不会提高，如果没有提高，我们不更新忍耐值，即并不杀怪。

int result = -1;
for (int j = 0; j <= s; ++j) {
    if (dp[0][j] >= 0) {//经验到达，忍耐度存在
        result = max(result, dp[0][j]);//找到最大的那个
    }
}

最后我们看的是dp[0][j]，就是不差经验，的时候，各种杀怪情况留下最大的忍耐度。

动态规划还挺抽象的，有必要多看几遍。