4.游戏智商(game.cpp)

Question

问题描述
熊的智商高还是猴子的智商高，这或许是一个很难考究的问题。故事里，吉吉国王一直
标榜自己是最聪明最伟大的猴子国王，他的毛毛也是这么坚信。而我们的熊大和熊二却一直
相信他们熊熊才是最聪明的。于是，在导游光头强的建议下，他们决定来一场 pk。
Pk 的内容是这样的，有 n 个格子，每个格子从左到右的编号依次是 1 到 n（编号也是位
置)，每个格子上都有不同美味值的水果（猴子们和熊们都很喜欢吃水果，所以水果对他们
来说很有吸引力）。他们从位置 0 开始出发，手上有 AB 两种卡片，A 卡有 na 张，B 卡片有
nb 张。每次他们可以用掉一张卡片，然后往前跳若干格，跳的格子数就是卡片上的数字。
每跳到一个格子上，就可以吃掉对应格子里面的水果，获得水果的美味值。当然了，我们会
保证当卡片用完的时候，一定刚好跳到第 n 个格子上。卡片一定要用完，不能有剩余。
游戏的结果就是在相同的情况下，谁能获得的水果美味值总和最大。熊熊们想要赢得这
个比赛，于是熊二请求你的帮助。如果你可以帮助他算出最大值，他甚至可以把他最心爱的
蜂蜜分享给你。
输入数据
输入文件 game.in：
输入第一行是 3 个整数 n，na，nb,va,vb，n 表示格子的总数，na 表示 A 种卡片的数量，
nb 表示 B 种卡片的数量，va 表示 A 种卡片上的数，vb 表示 B 种卡片上的数。保证 n 一定等
于 nava+nbvb。
接下来 n 个整数，表示每个格子上水果的美味值，注意美味值有可能是负数。
输出数据
输出文件 game.out：
输出只有一行一个整数，表示卡片用完的时候，最多可以得到的美味值总和。
输入输出样例 1
game.in
3 1 1 2 1
1 2 3
game.out
5
样例 1 解释
先用 1 再用 2，美味值是 4，先用 2 再用 1，美味值是 5。
输入输出样例 2
game.in
4 2 1 1 2
4 3 2 1
game.out
8
样例 2 解释
先用两个 1，再用 2，可以得到的值是 8。
数据范围约定
共计有 20 个测试点。
对于第 1-6 个测试点，保证 na=1,nb<=200，美味值都是小于等于 10000 的正整数。
对于第 7-12 个测试点，保证 1<=na,nb<=12，美味值的绝对值小于等于 10000。
对于 100%的数据，保证 1<=n<=20000,1<=na,nb<=2000,1<=va,vb<=5，va 不等于 vb，美
味值的绝对值不超过 1000000。
求c++代码！

Answer 1

该回答引用自GPT-3.5, 由博主 GISer Liu 编写：

好的，我们来详细分析并解决这个问题。

问题分析

这个问题可以看作是一个动态规划问题。我们需要找到一种使用卡片的方式，使得在到达第 n 个格子时，获得的美味值总和最大。

输入数据

• n：格子的总数
• na：A 种卡片的数量
• nb：B 种卡片的数量
• va：A 种卡片上的数
• vb：B 种卡片上的数
• 美味值数组：每个格子上水果的美味值

输出数据

• 一个整数，表示卡片用完的时候，最多可以得到的美味值总和。

解决思路

1. 状态定义：

   • 设 dp[i][j] 表示使用 i 张 A 卡片和 j 张 B 卡片时，能够获得的最大美味值。

2. 状态转移：

   • 对于每一张 A 卡片，我们可以跳 va 格；
   • 对于每一张 B 卡片，我们可以跳 vb 格；
   • 因此，状态转移方程为：

     dp[i][j] = max(dp[i-1][j] +美味值[i*va + j*vb], dp[i][j-1] +美味值[i*va + j*vb])
     

3. 初始化：

   • dp[0][0] = 0，表示没有使用任何卡片时，美味值为 0。

4. 结果输出：

   • 最终结果为 dp[na][nb]。

代码实现

下面是完整的 C++ 代码实现：

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
    // 读取输入数据
    int n, na, nb, va, vb;
    cin >> n >> na >> nb >> va >> vb;
    vector<int>美味值(n + 1);
    for (int i = 1; i <= n; ++i) {
        cin >> 美味值[i];
    }

    // 初始化动态规划数组
    vector<vector<int>> dp(na + 1, vector<int>(nb + 1, 0));

    // 动态规划填表
    for (int i = 0; i <= na; ++i) {
        for (int j = 0; j <= nb; ++j) {
            if (i > 0) {
                dp[i][j] = max(dp[i][j], dp[i - 1][j] + 美味值[i * va + j * vb]);
            }
            if (j > 0) {
                dp[i][j] = max(dp[i][j], dp[i][j - 1] + 美味值[i * va + j * vb]);
            }
        }
    }

    // 输出结果
    cout << dp[na][nb] << endl;

    return 0;
}

代码解释

1. 输入读取：

   • 读取 n, na, nb, va, vb 和美味值数组。

2. 动态规划数组初始化：

   • 使用二维数组 dp 来存储状态，初始值为 0。

3. 动态规划填表：

   • 使用两层循环遍历所有可能的 i 和 j 组合。
   • 根据状态转移方程更新 dp[i][j]。

4. 输出结果：

   • 最终结果存储在 dp[na][nb] 中，输出该值。

总结

通过上述分析和代码实现，我们可以有效地解决这个问题，帮助熊二计算出最大美味值总和。希望这个解决方案对你有所帮助！

如果该回答解决了您的问题，请采纳！如果没有，请私信联系或评论您的疑惑