GESP 题解库 / 6 级题解 / [GESP202603 六级] 选数 · 第 2 / 27 题
GESP202603 六级 · P15800 · 中等

选数

在下标跳跃约束 p(i+1) ≥ p(i) + b[p(i)] 下,最大化所选 a 的和。

📊
n ≤ 10⁵
数据规模
🔢
long long
数值类型
⚡
O(n)
时间复杂度
🎯
线性 DP + 后缀最大值
核心算法
01
题目拆解
把题目拆成一块块,看清全貌

📝 题目原文

给定两个长度为 n 的数组 a、b。要选出下标 p₁ < p₂ < … < p_k,满足:

在此前提下最大化 Σ a_(p_i)。

💡
人话翻译:这是一道典型的"选或不选"的线性 DP。设 dp[i] 表示"选了下标 i,且之后继续选下去能得到的最大和"。
那么 dp[i] = a[i] + (从 i + b[i] 之后最大的 dp)。用一个后缀最大值数组把"之后最大的 dp"做成 O(1) 查询。

🔍 关键词提取

线性 DP后缀最大值状态定义O(n) 递推

已知条件

项目说明
输入第一行 n;第二行 a₁…aₙ;第三行 b₁…bₙ
输出所选 a 之和的最大值
数据范围2 ≤ n ≤ 10⁵
a 的范围0 ≤ aᵢ ≤ 10⁹
b 的范围0 ≤ bᵢ ≤ n

需要解决的问题

02
思维导图
整理解题思路的全貌
🎯 dp[i] = a[i] + 之后最大的 dp
🧠 状态定义
dp[i]:必选 i 时的最大和
答案 = max 所有 dp[i]
转移只依赖更大的下标
所以可从右往左推
🔁 转移
下一个位置 j 需满足 j ≥ i + b[i]
且必须 j > i(严格递增)
所以 j ≥ max(i+1, i+b[i])
dp[i] = a[i] + 该范围内最大 dp
⚡ 加速
朴素转移是 O(n²)
维护后缀最大值 suf
suf[t] = max(dp[t..n])
查询变 O(1)
⚠️ 易错点
漏掉 j > i 导致 b[i]=0 时死循环
忘记可以和 0 取 max(后面一个都不选)
用 int(Σa 可达 10¹⁴)
答案没取全局最大值
03
样例手算推导
两个样例的 dp 推演

🧮 样例 1:a = [1,2,3,4],b = [3,3,1,1]

从右往左推。这里 suf[t] 表示 max(dp[t..n]),超出 n 时取 0。

1
i = 4

需要 j ≥ max(5, 4+1) = 5 → 没有可用位置

dp[4] = a[4] + 0 = 4

suf[4] = 4

dp[4] = 4

2
i = 3

b[3] = 1 → 需要 j ≥ max(4, 4) = 4

suf[4] = dp[4] = 4

dp[3] = a[3] + 4 = 3 + 4 = 7

suf[3] = max(dp[3], suf[4]) = max(7, 4) = 7

dp[3] = 7

3
i = 2

b[2] = 3 → 需要 j ≥ max(3, 5) = 5 → 无可用位置

dp[2] = a[2] + 0 = 2

suf[2] = max(2, 7) = 7

dp[2] = 2

4
i = 1

b[1] = 3 → 需要 j ≥ max(2, 4) = 4

suf[4] = 4

dp[1] = a[1] + 4 = 1 + 4 = 5

suf[1] = max(5, 7) = 7

dp[1] = 5

ia[i]b[i]j 的下界用到的 sufdp[i]
4415(越界)04
3314suf[4] = 47
2235(越界)02
1134suf[4] = 45

答案 = max(dp) = 7 ✓(选下标 3、4:3 + 4 = 7)

🧮 样例 2:a = [1,1,4,5,1,4],b = [1,2,3,2,1,0]

这次要留意 b[6] = 0 的边界。

1
i = 6(b[6] = 0 的关键案例)

b[6] = 0 → 单纯看 i + b[i] = 6,但下标必须严格递增

所以 j 的下界是 max(6+1, 6+0) = 7

没有可用位置 → dp[6] = a[6] = 4

如果忘了 j > i 这个条件,就会错误地允许再选一次 6(同一个下标),逻辑就崩了

dp[6] = 4

2
i = 5、4、3

i = 5:下界 max(6, 6) = 6 → suf[6] = 4 → dp[5] = 1 + 4 = 5

i = 4:下界 max(5, 6) = 6 → 4 → dp[4] = 5 + 4 = 9

i = 3:下界 max(4, 6) = 6 → 4 → dp[3] = 4 + 4 = 8

suf 更新:suf[5] = max(5,4) = 5;suf[4] = max(9,5) = 9;suf[3] = 9

dp = [?, ?, 8, 9, 5, 4]

3
i = 2、1

i = 2:下界 max(3, 4) = 4 → suf[4] = 9 → dp[2] = 1 + 9 = 10

i = 1:下界 max(2, 2) = 2 → suf[2] = max(10,9,5,4) = 10

→ dp[1] = 1 + 10 = 11

suf[1] = max(11, 10, 9, 5, 4) = 11

答案 11

i123456
dp[i]11108954

答案 = max(dp) = 11 ✓(选 1、2、4:1 + 1 + 5 = 7?)

🔑
找一组能达到 11 的方案:选下标 1、2、4、6:a₁ + a₂ + a₄ + a₆ = 1 + 1 + 5 + 4 = 11 ✓
验证约束:p₂ = 2 ≥ p₁ + b₁ = 1 + 1 = 2 ✓;p₃ = 4 ≥ p₂ + b₂ = 2 + 2 = 4 ✓;p₄ = 6 ≥ p₄ … 即 6 ≥ p₃ + b₄ = 4 + 2 = 6 ✓。完全满足条件。
04
解法对比
线性 DP vs 暴力枚举子集

⚔️ 解法对比

🟢 线性 DP + 后缀最大值(推荐) 推荐

从右往左算 dp[i],用 suf 数组 O(1) 查询后续最大 dp

  • 时间 O(n)
  • n = 10⁵ 时约 10⁵ 次
  • 代码 20 行
  • 空间 O(n)(可滚动数组优化)
💡
核心两行:dp[i] = a[i] + suf[max(i+1, i+b[i])];suf[i] = max(dp[i], suf[i+1]);注意 max(i+1, …) 里的 i+1 不能省(保证下标严格递增)。

🟠 枚举所有子集或所有下标组合

枚举所有合法的下标序列,取最大和

  • 可能的序列数量指数级
  • n = 10⁵ 完全不可行
  • 只能处理 n ≤ 20 左右
  • 完全不适合
⚠️
注意:本题的"选择"有顺序依赖(选了下标 i 就限定了下一个可以选的范围),这正是 DP 的典型特征。看到"选出一组满足位置约束的下标、使和最大",就该往 DP 想。

📈 性能对比

方案复杂度(n = 10⁵)可行性
线性 DP约 10⁵✅ 瞬间
枚举组合指数级❌ 不可行
05
算法流程图
从右往左递推并用后缀最大值加速
开始读入 n、数组 a、数组 b令 suf[n + 1] = 0;i = nt = max(i + 1, i + b[i])dp[i] = a[i] + suf[t](t 超过 n 时 suf 为 0)suf[i] = max(dp[i], suf[i + 1])i 是否已经减到 1?是 ✓输出 suf[1]否 ✗i 减 1,回到计算结束i 减 1 继续
← 左右滑动查看完整流程图
06
动手算一算
自己输入数据试试看

🎯 最大选取和计算器

第一行输入 a,第二行输入 b,程序会从右往左推出 dp 并给出答案。

结果会显示在这里

点按钮开始 →

07
代码精讲
逐段拆解,彻底搞懂

💻 完整 C++ 代码

#include <bits/stdc++.h>
using namespace std;

long long a[100005], dp[100005], suf[100005];
int b[100005];

int main() {
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) scanf("%lld", &a[i]);
    for (int i = 1; i <= n; i++) scanf("%d", &b[i]);

    suf[n + 1] = 0;                      // 越界时最大值为 0(后面一个都不选)

    for (int i = n; i >= 1; i--) {
        // 下一个可选位置:既要跳够 b[i],又要严格大于 i
        int t = max(i + 1, i + b[i]);
        long long best = (t <= n) ? suf[t] : 0;

        dp[i] = a[i] + best;
        suf[i] = max(dp[i], suf[i + 1]);
    }

    printf("%lld\n", suf[1]);            // suf[1] 就是所有 dp 的最大值
    return 0;
}
🔑
为什么 t = max(i + 1, i + b[i]) 里的 i + 1 不能省?当 b[i] = 0 时,i + b[i] = i,意思是"下一个下标 ≥ i"。但题目要求下标严格递增(p₁ < p₂ < …),所以至少要 i + 1。漏掉这个条件会允许"同一个下标被重复选用",逻辑就错了。

📖 关键几行怎么看

代码作用为什么这样写
suf[n+1] = 0哨兵越界时表示"后面不选任何数"
t = max(i + 1, i + b[i])下一个位置的下界兼顾"严格递增"和"跳够 b[i]"
dp[i] = a[i] + suf[t]转移必选 i,再加上后续最优
suf[i] = max(dp[i], suf[i+1])后缀最大值让查询 O(1)
printf("%lld", suf[1])输出suf[1] = max(dp[1..n])
⚠️
四个坑:① 忘记 max 里的 i + 1;② 用 int(Σa 可达 10⁵ × 10⁹ = 10¹⁴,必须 long long);③ 转移时忘了"可以和 0 取 max"(即后面一个都不选,用哨兵 suf[n+1] = 0 自然处理);④ 输出写成 dp[1](应该是 suf[1],因为最优解不一定从下标 1 开始)。
08
边界测试 & 易错点
把坑都踩一遍,考试不翻车

🧪 边界测试用例表

写完程序后,用这些数据自查一遍:

输入答案考察点
4
1 2 3 4
3 3 1 1
7题面样例 1(选 3、4)
6
1 1 4 5 1 4
1 2 3 2 1 0
11题面样例 2(选 1、2、4、6)
2
5 7
1 0
12b₁=1 允许选到 2,两个都能选
2
5 7
2 0
7b₁=2 时从 1 跳不到 2,只能选一个
3
0 0 0
0 0 0
0全是 0,答案 0
5
9 1 1 1 9
4 0 0 0 0
18b₁=4 允许从 1 直接跳到 5,取 9 + 9 = 18
✅
自查清单:① 写了 max(i+1, …) 吗?② 用 long long 吗?③ 输出 suf[1] 吗?

🚨 易错点清单

⚠️
漏掉 i + 1:b[i] = 0 时下标可能不递增,必须用 max(i+1, i+b[i])。
⚠️
用 int:aᵢ ≤ 10⁹、n ≤ 10⁵,总和可达 10¹⁴,必须 long long。
⚠️
输出 dp[1]:最优解不一定从下标 1 开始,应输出 suf[1]。
09
复杂度分析
算算效率怎么样

📊 复杂度四宫格

时间复杂度
O(n)
空间复杂度
O(n)
n 最大
10⁵
运算量
约 10⁵

时间怎么算的?

空间都用在哪?

数组 a、b、dp、suf 各 O(n)。实际上可以只保留 suf,把空间降到 O(n) 常数级(滚动)。

✅ 约 10 万次运算,瞬间完成。关键是"从右往左推 + 后缀最大值"这个组合。

10
知识拓展
学一道题,会一类题

🔗 常用技巧小抄

// 本题的 DP 骨架
suf[n + 1] = 0;
for (int i = n; i >= 1; i--) {
    int t = max(i + 1, i + b[i]);
    dp[i] = a[i] + (t <= n ? suf[t] : 0);
    suf[i] = max(dp[i], suf[i + 1]);
}
// 答案 = suf[1]

// 类似"选一批满足位置约束的下标"的题都可以这样设计状态
// 关键点:让"下一个位置的范围"能被当前状态确定

// 后缀最大值 / 前缀最大值 是 DP 优化的常用手段
// 把 O(n) 的区间查询压成 O(1)
for (int i = n; i >= 1; i--) suf[i] = max(a[i], suf[i + 1]);   // 后缀最大
for (int i = 1; i <= n; i++) pre[i] = max(a[i], pre[i - 1]);   // 前缀最大

🌟 举一反三

把这道题用到的基本功拆出来,它们能迁移到很多同类问题上。

能力点本题怎么用还能迁移到
线性 DP状态 + 转移 + 边界所有"选/不选"的序列问题
后缀最大值O(1) 查询区间最值所有转移需要"后续最优"的 DP
严格递增约束max(i+1, …)下标/位置必须递增的题
🌟
思考题:如果约束改成"p_(i+1) ≥ p_i + b_(p_i) 且还要 a_(p_i) ≥ a_(p_(i+1))"(选出的 a 值单调不增),上面的 DP 还成立吗?(提示:不再直接成立——因为转移时"能不能选 j"不仅取决于位置,还取决于"上一个选的 a 值",需要把状态扩展成 dp[i][值] 或用其他数据结构优化。约束一旦和"值"挂钩,状态空间就会膨胀。)