最大得分 - 跳格子游戏算法题解

{"title":"最大得分 - 跳格子游戏算法题解","description":"本题是一个经典的动态规划问题，要求你在一个长度为n的格子序列中，每次可以选择向前跳1格或2格，并获得该格子的数字作为得分，最终要求你获得的最大得分。题目包含C++代码示例，详细解析了算法思路。","keywords":"动态规划, 跳格子, 算法题, 最大得分, C++代码, 算法思路","content":""地面上有一排长度为 n 的格子 1−n，每个格子上都有一个数 x i ，开始时你在位置 0 ，每次你可以向前跳 1-2 格，然后取走格子上的数，直到跳到位置 n+1。\n\n取走的数的和就是你的得分，现在你想知道你可能的最大得分是多少。\n\n输入\n一行四个整数 n,A,B,C (n≤100000, 0≤A,B,C≤10000)，其中n表示格子的数量。\n\nx[i] 由如下方式生成：\n\n for (int i = 1; i <= n; i++){\n \t int tmp = ((long long)A * i * i + B * i + C) % 20000;\n \t x[i] = tmp - 10000;\n }\n\n输出\n一行一个整数 ans 表示可能的最大得分。\n\n样例\n输入复制\n3 1 1 1\n输出复制\n-9993\nc++ 代码内容：cpp\\n#include <iostream>\\n#include <vector>\\n#include <algorithm>\\nusing namespace std;\\n\\nint main() {\\n int n, A, B, C;\\n cin >> n >> A >> B >> C;\\n \\n vector<int> x(n+1);\\n for (int i = 1; i <= n; i++) {\\n int tmp = ((long long)A * i * i + B * i + C) % 20000;\\n x[i] = tmp - 10000;\\n }\\n \\n vector<int> dp(n+2);\\n dp[0] = 0;\\n dp[1] = x[1];\\n for (int i = 2; i <= n+1; i++) {\\n dp[i] = max(dp[i-1], dp[i-2]) + x[i];\\n }\\n \\n cout << dp[n+1] << endl;\\n \\n return 0;\\n}\\n\n"}