C++【动态规划2】跳跳棋

Question

麻烦回答下问题THANKS

C++【动态规划2】跳跳棋
题目难度：普及-
时间限制：1000ms
内存限制：512MB
【题目描述】
小T作为班级的班长，承担着班级的各项事务，今天班主任交给了小T一个重要的任务，学校的知识竞赛就要开始了，要小T代表班级去参加，今天这场是跳跳棋，跳跳棋的棋盘长度为n，排成一排，每个格子上都有一个数字ai，在游戏的开始，小T可以选择一个位置i，这是小T的初始位置，然后小T可以获得ai的得分，并且跳到i+ai的位置j之后，继续获得aj的得分，再跳到j+aj的位置上，直到小T跳出棋盘，则游戏结束，将小T获得的分数累加就是他最终的得分，现在小T想赢得比赛的胜利，需要知道他可以获得的最大得分，由于这个问题太难了，小T才小学一年级，还算不过来，需要你帮帮他。
【输入格式】
第一行一个整数t表示测试数据组数。

接下来每组数据的第一行为一个整数n，表示棋盘长度。

接下来一行包含n个整数，分别为a1到an。
【输出格式】
t行，对于每组数据，输出最大得分。

【样例输入#1】
4
5
7 3 1 2 3
3
2 1 4
6
2 1000 2 3 995 1
5
1 1 1 1 1
​
【样例输出#1】
7
6
1000
5
​
【大样例】
down1.in/down1.out
【数据范围】
对于30%的数据，1≤n≤10。
对于50%的数据，1≤n≤10^3 。
对于100%的数据，1≤ai,n≤2∗10^4,1≤t≤10。

真的急啊

Answer 1

下午好🌅🌅🌅
本答案参考通义千问

好的，我们可以通过动态规划的方法来解决这个问题。我们需要找到一种方法来计算小T可以获得的最大得分。下面是一个详细的解答步骤：

动态规划思路

1. 定义状态：

   • dp[i] 表示从位置 i 开始，可以获得的最大得分。

2. 状态转移方程：

   • 如果从位置 i 跳到位置 j，则 dp[i] = a[i] + dp[j]，其中 j = i + a[i]。
   • 如果 j 超出棋盘边界，则直接取 dp[i] = a[i]。

3. 初始化：

   • 对于每个位置 i，如果 i + a[i] 超出边界，则 dp[i] = a[i]。
   • 否则，初始化 dp[i] 为 0，因为我们需要通过后续的转移来更新这个值。

4. 结果：

   • 最终答案是 dp 数组中的最大值。

代码实现

下面是用 C++ 实现的代码：

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

using namespace std;

int main() {
    int t;
    cin >> t;

    while (t--) {
        int n;
        cin >> n;

        vector<int> a(n);
        for (int i = 0; i < n; ++i) {
            cin >> a[i];
        }

        vector<int> dp(n, 0);

        for (int i = n - 1; i >= 0; --i) {
            int jump = i + a[i];
            if (jump >= n) {
                dp[i] = a[i];
            } else {
                dp[i] = a[i] + dp[jump];
            }
        }

        cout << *max_element(dp.begin(), dp.end()) << endl;
    }

    return 0;
}

代码解释

1. 输入处理：

   • 读取测试数据组数 t。
   • 对于每组数据，读取棋盘长度 n 和每个格子上的数字 a[i]。

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

   • dp 数组初始化为 0。

3. 状态转移：

   • 从后往前遍历每个位置 i，计算 jump = i + a[i]。
   • 如果 jump 超出边界，则 dp[i] = a[i]。
   • 否则，dp[i] = a[i] + dp[jump]。

4. 输出结果：

   • 输出 dp 数组中的最大值。

这样，我们就可以得到小T可以获得的最大得分。希望这个解答对你有帮助！