【GESP】C++六级真题 luogu-P15800, [GESP202603 六级] 选数

2026年3月，GESP六级真题，考察线性动态规划，难度⭐⭐★☆☆。洛谷难度等级：普及/提高−。

P15800 [GESP202603 六级] 选数

题目要求

题目描述

给定两个包含 $n$ 个整数的数组 $a=[a_1,\dots,a_n]$ 与 $b=[b_1,\dots,b_n]$。你需要指定若干下标 $p_1\lt \cdots\lt p_k$（$1\leq k\leq n$）使得以下条件成立：

• $1\leq p_i\leq n$（$1\leq i\leq k$）；
• $p_{i+1}\geq p_i+b_{p_i}$（$1\leq i\leq k$）。

你需要在满足以上条件的前提下最大化 $\sum_{i=1}^k a_{p_i}$，也即最大化数组 $a$ 对应下标的整数之和。

（注：题目原描述中 $\sum_{i=1}^k a_{p_k}$ 应为笔误，根据题意及输入输出样例，实际为求和 $\sum_{i=1}^k a_{p_i}$）

输入格式

第一行，一个正整数 $n$，表示数组长度。

第二行，$n$ 个正整数 $a_1,a_2,\dots,a_n$，表示数组 $a$。

第三行，$n$ 个正整数 $b_1,b_2,\dots,b_n$，表示数组 $b$。

输出格式

一行，一个整数，表示在满足下标条件的前提下，数组 $a$ 对应下标的整数之和的最大值。

输入输出样例 #1

输入 #1

4
1 2 3 4
3 3 1 1

输出 #1

7

输入输出样例 #2

输入 #2

6
1 1 4 5 1 4
1 2 3 2 1 0

输出 #2

11

说明/提示

对于 $40\%$ 的测试点，保证 $2\leq n\leq 10^3$。

对于所有测试点，保证 $2\leq n\leq 10^5$，$0\leq a_i\leq 10^9$，$0\leq b_i\leq n$。

---

题目分析

这道题考察了动态规划（DP）的思想。题目要求我们在数组中选择若干个元素，使得它们的和最大，并且如果选择了下标为 $p_i$ 的元素，下一个选择的元素下标 $p_{i+1}$ 必须满足 $p_{i+1} \ge p_i + b_{p_i}$，且由于序列必须递增，同时显然还要满足 $p_{i+1} > p_i$。

1. 状态定义： 定义 dp[i] 为在后缀数组 $a[i \dots n]$ 中进行选择，所能得到的最大和。

2. 状态转移方程： 对于第 $i$ 个元素，我们有两种选择：
   • 不选第 $i$ 个元素：那么最大和就是从 $i+1$ 到 $n$ 中选择的最大和，即 dp[i+1]。
   • 选第 $i$ 个元素：那么我们获得了 $a_i$ 的价值，下一个能选的元素下标必须至少是 $\max(i+1, i+b_i)$。那么从这个合法的下一个位置到 $n$ 的最大和就是 dp[next_idx]，其中 next_idx = max(i + 1, i + b[i])。

   综合上述两种情况，状态转移方程为： \(dp[i] = \max(dp[i+1], a_i + dp[\min(n + 1, \max(i + 1, i + b_i))])\)

3. 初始状态与遍历顺序： 由于计算 dp[i] 时需要用到它后面的状态 dp[i+1] 以及 dp[next_idx]，我们需要从后往前逆序遍历（即从 $n$ 到 $1$）。 超出数组范围的 dp[n+1] 等初始化为 $0$。

4. 数据范围注意： 题目给出 $n \le 10^5$，$a_i \le 10^9$。如果全选，最大和可能达到 $10^{14}$，超过了 32 位有符号整数 int 的表示范围（最大约 $2 \times 10^9$），因此 dp 数组必须使用 long long 类型。

---

示例代码

标准解法（动态规划）

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


// 使用 long long 防止累加结果溢出
typedef long long ll;

const int MAXN = 100005;
ll a[MAXN];
int b[MAXN];
ll dp[MAXN * 2]; // 稍微开大一点防止越界

int main() {
    // 优化输入输出速度
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n;
    std::cin >> n;

    for (int i = 1; i <= n; i++) {
        std::cin >> a[i];
    }
    for (int i = 1; i <= n; i++) {
        std::cin >> b[i];
    }

    // 从后往前计算 DP
    // dp 数组默认全为 0，dp[n+1] 开始往后都是 0，作为边界条件
    for (int i = n; i >= 1; i--) {
        // 下一个可以选择的位置
        // 注意：除了满足题目给出的 i + b[i]，还必须严格大于当前位置 i
        int next_idx = std::max(i + 1, i + b[i]);
        if (next_idx > n + 1) {
            next_idx = n + 1; // 越界部分当作 n + 1 处理，对应 dp 值为 0
        }

        // 状态转移：取“不选当前元素”和“选当前元素”的最大值
        dp[i] = std::max(dp[i + 1], a[i] + dp[next_idx]);
    }

    // dp[1] 即为在整个数组 1...n 中选择的最大和
    std::cout << dp[1] << "\n";

    return 0;
}

代码解析小贴士

1. 逆向思维：很多序列选择类的动态规划题目，如果从前往后定义状态比较复杂（因为要记录上一个选了什么，可能会导致状态维数增加或者转移过程很绕），可以尝试从后往前定义 dp[i] 表示“从 $i$ 开始到末尾的最大价值”，这样状态转移只依赖后面的结果，逻辑会清晰得多。
2. 数据类型溢出：在 GESP 考级或信奥赛中，看到数值范围 $10^9$，基本可以判定累加和会超过 int 上限，果断开 long long 是避免只拿部分分的好习惯。

所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code

GESP 学习专题站：GESP WIKI

"luogu-"系列题目可在洛谷题库进行在线评测。

"bcqm-"系列题目可在编程启蒙题库进行在线评测。

欢迎加入：Java、C++、Python技术交流QQ群(982860385)，大佬免费带队，有问必答

欢迎加入：C++ GESP/CSP认证学习QQ频道，考试资源总结汇总

欢迎加入：C++ GESP/CSP学习交流QQ群(688906745)，考试认证学员交流，互帮互助

GESP/CSP 认证学习微信公众号