GESP2026年3月认证C++六级真题与解析（编程题1 选数）

这道题真正考的是：

动态规划（DP）

而且是非常经典的：

线性DP + 跳跃转移

一、题目讲了什么？

1、题目给了两个数组：

a[] b[]

2、例如样例：

a: 1 2 3 4 b: 3 3 1 1

3、题目允许我们选择一些位置。

（1）假如选了位置 i：

获得：

a[i]

分数。

（2）但是代价是：

会跳过后面若干位置。

（3）跳过多少？

由：

b[i]

决定。

二、故事理解

1、想象有一条糖果街。

位置: 1 2 3 4 糖果: 1 2 3 4

2、每个位置还有一个魔法数字：

3 3 1 1

3、如果你站在第1格：

糖果=1 跳跃=3

拿走糖果后：

获得1分

然后必须跳到：

1+3=4

位置。

4、如果站在第2格：

获得2分

然后跳到：

2+3=5

超出范围。

5、目标：

获得最多糖果

三、DP状态定义

1、定义：

f[i]

表示：

到达位置 i 时，之前已经获得的最大分数。

2、比如：

f[4]=10

意思：

来到4号位置前 已经赚了10分

3、注意：

还没拿4号位置的糖果。

四、两种选择

来到 i。

有两种情况。

选择1：拿糖果

获得：

a[i]

分。

然后跳到：

i+b[i]

位置。

于是：

f[i+b[i]] = max( f[i+b[i]], f[i]+a[i] )

意思：

把当前糖果拿走 然后跳过去

选择2：不拿糖果

直接走到下一格。

f[i+1] = max( f[i+1], f[i] )

意思：

这格不要 继续往前

五、手算样例

1、样例：

4 a: 1 2 3 4 b: 3 3 1 1

2、初始：

f: 0 0 0 0

（1）i=1

拿：

得1分

跳：

1+3=4

所以：

f[4]=1

不拿：

f[2]=0

现在：

f: 0 0 0 1

（2）i=2

拿：

2+3=5

越界。

不能。

不拿：

f[3]=0

（3）i=3

拿：

得3分

跳：

3+1=4

于是：

f[4] =max(1,3) =3

（4）i=4

已有：

f[4]=3

拿：

3+4 = 7

（5）答案：

7

六、为什么不是贪心

很多同学会想：

每次选最大的糖果

例如：

10 1 1 100

可能：

拿10

后面就跳飞了。

失去：

100

因此：

局部最优

≠

全局最优

所以必须DP。

七、参考代码

官方代码：

#include <cstdio> #include <algorithm> using namespace std; const int N = 100005; int n; int a[N]; int b[N]; long long f[N]; long long ans; int main() { scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) scanf("%d",&b[i]); for(int i=1;i<=n;i++) { ans=max(ans,f[i]+a[i]); // 选当前位置 if(i+b[i]<=n) { f[i+b[i]] = max( f[i+b[i]], f[i]+a[i] ); } // 不选当前位置 f[i+1] = max( f[i+1], f[i] ); } printf("%lld\n",ans); return 0; }

八、本题考点

1、本题经典模型：

走到位置 i ↓ 做决策 ↓ 跳到新位置 ↓ 继续DP

2、结构：

dp[下一状态] = max( dp[下一状态], dp[当前状态]+收益 );

九、记忆口诀

1、看到：

一条线 从左到右 每个位置有收益 选择后跳到新位置 求最大收益

2、立刻想到：

线性DP 状态转移