c++回溯 超级马里奥1

Question

题目描述
米饭大魔王沉迷于马里奥无法自拔，所以在出题过程中抄了一个马里奥的题目。
已知在一条直线上有n+1个点，分别为0,1,2,..,n。除初始点0之外，其他每个点到达之后都会有一些金币奖励或金币惩罚，（用正数表示奖励，负数表示惩罚）。
大魔王的马里奥只会从左向右跳，从不回头，且每次可以跳跃的最短距离为x，最长距离为y。
当前已知点的个数，每个点的奖励或惩罚及跳跃的最短距离x最长距离y，询问从点0跳到点n可以获得的最大奖励是多少？

输入格式
第一行一个整数数字n，表示坐标轴上共有n个点。
第二行共n个整数，表示点1,2,3,..,n每个点对应的奖励或惩罚。
第三行两个整数x和y，表示马里奥每次跳跃的最小和最大距离。
数据范围
n＜=25，y-x＜=n
输出格式
输出一个num，表示从点0跳到点n可以获得的最大金币奖励数

样例输入
10
1 2 3 4 5 6 7 8 9 10
2 3
样例输出
30

Answer 1

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

根据题目描述，这是一个典型的动态规划问题。我们可以使用动态规划来解决。具体思路如下：

1. 创建一个大小为n+1的数组dp，其中dp[i]表示从点0跳到点i可以获得的最大金币奖励数。
2. 初始化dp[0]为点0的奖励或惩罚值，即dp[0] = rewards[0]。
3. 从点1开始遍历到点n，对于每个点i，计算dp[i]的值：

• 遍历点i之前的所有可能的起跳点j，j的取值范围为[i-y, i-x]，保证跳跃距离在x到y之间。
• 对于每个起跳点j，计算从j跳到i的奖励值，并选择奖励最大的情况更新dp[i]，即dp[i] = max(dp[i], dp[j] + rewards[i])。

1. 最终返回dp[n]，即从点0跳到点n可以获得的最大金币奖励数。
   具体实现代码如下：
   cppCopy code

   #include <iostream>
   #include <vector>
   using namespace std;
   int maxCoins(int n, vector<int>& rewards, int x, int y) {
   vector<int> dp(n + 1);
   dp[0] = rewards[0];
   for (int i = 1; i <= n; ++i) {
   dp[i] = INT_MIN;
   for (int j = max(0, i - y); j <= i - x; ++j) {
   dp[i] = max(dp[i], dp[j] + rewards[i]);
   }
   }
   return dp[n];
   }
   int main() {
   int n;
   cin >> n;
   vector<int> rewards(n + 1);
   for (int i = 1; i <= n; ++i) {
   cin >> rewards[i];
   }
   int x, y;
   cin >> x >> y;
   int result = maxCoins(n, rewards, x, y);
   cout << result << endl;
   return 0;
   }
   

   这段代码实现了题目描述的功能。你可以将其粘贴到C++的环境中运行。

如果该回答解决了您的问题，请采纳！如果没有，请参考以下方案进行修订