202603-选数(luogu-P15800)

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

输入输出样例 #2

输入 #2

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

输出 #2

说明/提示

对于 $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$ 。

状态定义：定义 dp[i] 为在后缀数组 $a[i \dots n]$ 中进行选择，所能得到的最大和。
状态转移方程：对于第 $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))])$
初始状态与遍历顺序：由于计算 dp[i] 时需要用到它后面的状态 dp[i+1] 以及 dp[next_idx]，我们需要从后往前逆序遍历（即从 $n$ 到 $1$ ）。超出数组范围的 dp[n+1] 等初始化为 $0$ 。
数据范围注意：题目给出 $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;
}

代码解析小贴士

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

本文由coderli.com原创，按照CC BY-NC-SA 4.0 进行授权
所有代码已上传至Github：https://github.com/lihongzheshuai/yummy-code
“luogu-”系列题目可在 洛谷题库 在线评测。
“bcqm-”系列题目可在 编程启蒙题库 在线评测。

GESP/CSP认证交流QQ群： 688906745

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

最后更新于 2026年3月20日

202603-完全二叉树(luogu-P15801)