C++最多奖励（win）

Question

卡卡西果然不负众望，很快就将“园区最受欢迎指数”问题迎刃而解，此时，天空中出现一道金光，照的小朋友们都睁不开眼睛，卡卡西发现所有小朋友手上的动物园门票都慢慢变的清晰起来，并且升至空中，聚集在一起，形成一个巨大的彩虹形状的大桥……这是梦吗？小朋友们都不敢相信自己的眼睛，努力的揉着眼睛。是的，是真的！这些手中的门票，合在一起变成了一座七彩桥，来迎接小朋友们去动物园呢！卡卡西带着小朋友们，相继和植物园的叔叔阿姨们再见，然后有条不紊的走上了桥……

没多久功夫，动物园就到了，卡卡西和小伙伴们走下了大桥。可是好奇怪啊，本该热闹非凡的动物园怎么安安静静的，什么活动都没有，大门也紧锁着。小朋友们的心里有点害怕，仔细观察了下，卡卡西在大门外发现了一张告示，上面贴着一道题目，原来动物园园长被困在了迷宫里，由神秘的绿巨人守卫着，他出了一道题目，如果有人能破解此题，就释放园长！题目是这样的：假设现在要从城堡A经过若干障碍到达城堡B，每经过一个障碍都要消耗一定的能量，但也有一定的奖励。人们可以经过传送门到达任意障碍处，那么在有限的能量内，该如何选择障碍，使得到达城堡B时获得的奖励最多。

卡卡西咬咬牙，坚定的说：“小伙伴们，咱们一定要努力破解此题，救出园长！”聪明的小朋友们，你们能帮忙解救园长吗？

输入：输入数据有3行，第1行有2个用空格分开的数，表示出发时的能量a和障碍数目n；第2行有n个用空格分开的数，其中，第i个数表示清除第i个障碍所需能量；第3行有n个用空格分开的数，其中，第i个数表示清除第i个障碍获得的奖励。

输出：最多的奖励。

样例：

输入：（win.in）

10 5

2 3 4 2 5

1 7 4 3 4

输出： (win.out)

14

数据范围:

0<a<=1000 0<n<=100 0<障碍所需能量，奖励<100

Answer 1

以下回复参考：皆我百晓生、券券喵儿等免费微信小程序作答:

这是一个典型的动态规划问题，我们可以使用动态规划来解决这个问题。假设我们的能量为 E，当前的位置为 P，最大的奖励为 R。我们的目标是找到一条路径，使得在能量耗尽之前，我们能获得最大的奖励。这是一个典型的背包问题的变种，每个障碍可以看作是一个物品，其重量是清除它所需的能量，其价值是清除它获得的奖励。我们可以将问题转化为如何在总重量不超过出发时能量的前提下，最大化价值的问题。我们可以使用一个二维数组 dp[i][j]，其中 i 表示我们当前考虑的障碍数，j 表示我们当前剩余的能量。dp[i][j] 的值表示在考虑到第 i 个障碍并且剩余能量为 j 时我们能获得的最大奖励。初始时，dp[0][a] = 0（没有考虑任何障碍时的奖励为 0）。我们的目标是找到 dp[n][a]，即在考虑了所有的障碍并且剩余能量恰好为出发时的能量时我们能获得的最大奖励。转移方程为：dp[i][j] = max(dp[i-1][j], dp[i-1][j-cost[i]] + reward[i])，其中 cost[i] 表示清除第 i 个障碍所需的能量，reward[i] 表示清除第 i 个障碍获得的奖励。具体的算法如下：

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

int main() {
    int a, n;
    cin >> a >> n;
    vector<int> cost(n), reward(n);  // cost 是清除每个障碍所需的能量，reward 是清除每个障碍获得的奖励
    for (int i = 0; i < n; ++i) cin >> cost[i];
    for (int i = 0; i < n; ++i) cin >> reward[i];
    vector<vector<int>> dp(n + 1, vector<int>(a + 1, 0));  // dp[i][j] 表示考虑到第 i 个障碍并且剩余能量为 j 时我们能获得的最大奖励
    for (int i = 1; i <= n; ++i) {  // 从第一个障碍开始考虑
        for (int j = a; j >= cost[i - 1]; --j) {  // 从最大的能量开始考虑，如果当前能量不足以清除这个障碍，那么就没有必要考虑这个障碍
            dp[i][j] = max(dp[i - 1][j], dp[i - 1][j - cost[i - 1]] + reward[i - 1]);  // 更新 dp 值
        }
    }
    cout << dp[n][a] << endl;  // 输出最多的奖励
    return 0;
}

注意这个算法的时间复杂度是 O(n*a)，其中 n 是障碍的数量，a 是出发时的能量。在这个问题中，n 和 a 的最大值是 100 和 1000，所以这个算法可以在几秒内得到结果。