选数 题解

题目分析

我们有两个长度为 $n$ 的数组 $a$ 和 $b$，要求选出一组递增的下标 $p_1<p_2<\cdots <p_k$，满足相邻下标之间的约束：

也就是说，当你选择了下标 $p_i$ 后，下一个下标至少要跳到 $p_i + b_{p_i}$。如果有多个下标满足条件，我们可以自由选择其中任意一个。目标是最大化所选位置的 $a$ 值之和。

数据范围：$n \le 10^5$，$a_i$ 可达 $10^9$，$b_i$ 在 $[0, n]$ 内。我们需要在 $O(n)$ 或 $O(n \log n)$ 的时间内完成计算。

解题思路

状态定义

由于每一步的选择只依赖当前下标以及它的 $b$ 值，并且我们总是从前向后决策，可以考虑动态规划。

设 $f[i]$ 表示：在位置 $i$ 可以作为下一个被选位置的前提下，前面已经选过的元素能获得的最大总和（注意 $f[i]$ 不包含 $a_i$）。

状态转移

当我们从小到大扫描到位置 $i$ 时，$f[i]$ 已经包含了前面若干位置作为“最后选择”后传递过来的最优值。在位置 $i$ 我们有两种决策：

1. 选择位置 $i$
   此时我们可以得到总和 $f[i] + a_i$，并把它作为最终的候选答案之一。
   同时，由于选择了 $i$，下一个可以选的位置必须至少是 $i + b_i$。因此我们可以将新的状态传递给 $f[i + b_i]$：
   

   $$f[i+b_i]=\max (f[i+b_i],f[i]+a_i)$$

2. 不选择位置 $i$
   如果当前位置不选，那么下一个位置 $i+1$ 直接继承“可以被选”的资格，并且已获得的总和不变：
   

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

初始时，位置 $1$ 可以被选且前面总和为 $0$，即 $f[1] = 0$。其余 $f[i]$ 初始为 $0$（因为可能从某些 $i + b_i$ 直接跳过来，这也是合理的，相当于前面不选任何元素，直接从该位置开始选）。

遍历顺序自然是从 $1$ 到 $n$。

最终答案

所有“选择位置 $i$” 产生的 $f[i] + a_i$ 中的最大值即为答案。由于 $a_i \ge 0$，我们也可以在遍历过程中顺带维护全局最大值。

算法说明

下面结合参考代码进行说明（C++ 实现）：

cpp
复制
1#include <cstdio>
2#include <algorithm>
3using namespace std;
4const int N = 1e5 + 5;
5int n;
6int a[N], b[N];
7long long f[N], ans;          // f 可能很大，用 long long
8int main() {
9    scanf("%d", &n);
10    for (int i = 1; i <= n; i++)
11        scanf("%d", &a[i]);
12    for (int i = 1; i <= n; i++)
13        scanf("%d", &b[i]);
14
15    for (int i = 1; i <= n; i++) {
16        ans = max(ans, f[i] + a[i]);             // 决策1：选择 i，更新答案
17        if (i + b[i] <= n)                        // 边界判断，防止越界
18            f[i + b[i]] = max(f[i + b[i]], f[i] + a[i]); // 选择 i 后，传递给 i+b[i]
19        f[i + 1] = max(f[i + 1], f[i]);          // 决策2：不选 i，传递给 i+1
20    }
21    printf("%lld\n", ans);
22    return 0;
23}

代码解析：

• f[i] 表示在位置 $i$ 可以作为下一个选择时的最大前缀和（不含 $a_i$）。
• 每轮循环，首先尝试在 $i$ 处选择：用 f[i] + a[i] 尝试更新答案，这是因为如果选了 $i$ 后不再往后选择，这便是一种合法的终止状态。
• 如果选择了 $i$，则下一跳至少是 $i + b_i$，因此用 f[i] + a[i] 去更新 f[i + b_i]。
• 如果不选 $i$，则状态直接“滑动”到下一个位置 $i+1$，f[i+1] 继承 f[i] 的值（取较大者）。
• 边界处理：i + b[i] 可能超过 $n$，此时下一跳直接超出数组，无法再选后续元素，但不影响前面所得答案。

时间复杂度分析

整个算法只对数组进行了一次线性扫描，每次循环内执行常数次比较和赋值操作，因此时间复杂度为 $O(n)$。
空间复杂度也为 $O(n)$，主要用来存储数组 $a$、$b$ 和 $f$。

对于 $n \le 10^5$，该算法在 1s 时间限制和 256MB 内存限制内完全可以高效运行。

总结

这道题的关键在于抓住约束条件中的单调性：$p_{i+1} \ge p_i + b_{p_i}$ 保证了状态只能向后传递，且 $b_i \ge 0$ 使得不会出现回跳。因此可以设计一维 DP，顺序扫描，通过“选择当前”和“跳过当前”两种操作更新后续状态。这类“跳跃选数”模型在竞赛中较为常见，掌握这种线性递推的 DP 方法，对解决类似问题很有帮助。