在下标跳跃约束 p(i+1) ≥ p(i) + b[p(i)] 下,最大化所选 a 的和。
给定两个长度为 n 的数组 a、b。要选出下标 p₁ < p₂ < … < p_k,满足:
1 ≤ p_i ≤ np_(i+1) ≥ p_i + b_(p_i)——下一个下标必须"跳过"至少 b 个位置在此前提下最大化 Σ a_(p_i)。
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 |
dp[i] = 从 i 出发(必须选 i)能取到的最大和dp[i] = a[i] + max(0, max{dp[j] : j ≥ i + b[i], j > i})j > i?因为下标必须严格递增;b[i] = 0 时只靠 i + b[i] = i 不能保证递增suf[i] = max(dp[i], dp[i+1], …, dp[n])从右往左推。这里 suf[t] 表示 max(dp[t..n]),超出 n 时取 0。
需要 j ≥ max(5, 4+1) = 5 → 没有可用位置
dp[4] = a[4] + 0 = 4
suf[4] = 4
dp[4] = 4
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
b[2] = 3 → 需要 j ≥ max(3, 5) = 5 → 无可用位置
dp[2] = a[2] + 0 = 2
suf[2] = max(2, 7) = 7
dp[2] = 2
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
| i | a[i] | b[i] | j 的下界 | 用到的 suf | dp[i] |
|---|---|---|---|---|---|
| 4 | 4 | 1 | 5(越界) | 0 | 4 |
| 3 | 3 | 1 | 4 | suf[4] = 4 | 7 |
| 2 | 2 | 3 | 5(越界) | 0 | 2 |
| 1 | 1 | 3 | 4 | suf[4] = 4 | 5 |
答案 = max(dp) = 7 ✓(选下标 3、4:3 + 4 = 7)
这次要留意 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
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]
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
| i | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| dp[i] | 11 | 10 | 8 | 9 | 5 | 4 |
答案 = max(dp) = 11 ✓(选 1、2、4:1 + 1 + 5 = 7?)
从右往左算 dp[i],用 suf 数组 O(1) 查询后续最大 dp
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⁵) | 可行性 |
|---|---|---|
| 线性 DP | 约 10⁵ | ✅ 瞬间 |
| 枚举组合 | 指数级 | ❌ 不可行 |
第一行输入 a,第二行输入 b,程序会从右往左推出 dp 并给出答案。
点按钮开始 →
#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 开始)。写完程序后,用这些数据自查一遍:
| 输入 | 答案 | 考察点 |
|---|---|---|
4 | 7 | 题面样例 1(选 3、4) |
6 | 11 | 题面样例 2(选 1、2、4、6) |
2 | 12 | b₁=1 允许选到 2,两个都能选 |
2 | 7 | b₁=2 时从 1 跳不到 2,只能选一个 |
3 | 0 | 全是 0,答案 0 |
5 | 18 | b₁=4 允许从 1 直接跳到 5,取 9 + 9 = 18 |
max(i+1, …) 吗?② 用 long long 吗?③ 输出 suf[1] 吗?i + 1:b[i] = 0 时下标可能不递增,必须用 max(i+1, i+b[i])。suf[1]。数组 a、b、dp、suf 各 O(n)。实际上可以只保留 suf,把空间降到 O(n) 常数级(滚动)。
✅ 约 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][值] 或用其他数据结构优化。约束一旦和"值"挂钩,状态空间就会膨胀。)