选数题解（倒推）

这道题我用的倒推的方法

---

---

题目大意

给定两个长度为 $n$ 的数组 $a$ 和 $b$，你需要选择一个下标序列 $p_1 < p_2 < \dots < p_k$，满足：

• $p_{i+1} \ge p_i + b_{p_i}$

求 $\sum a_{p_i}$ 的最大值。

---

思路分析

1. 暴力 DP

定义 $dp[i]$ 表示以第 $i$ 个位置作为最后一个选择时，能获得的最大金币数。

转移方程：

$$dp[i] = a[i] + \max_{j < i,\ j + b[j] \le i} dp[j]$$

最终答案：

$$ans = \max_{1 \le i \le n} dp[i]$$

直接枚举所有 $j$ 的复杂度是 $O(n)$，会超时。

---

2. 优化思路

观察转移条件 $j + b[j] \le i$：

• 随着 $i$ 的增大，满足条件的 $j$ 只会增加，不会减少
• 我们可以动态维护一个变量 best，表示‌当前所有已生效的 $dp[j]$ 的最大值‌

关键问题：如何判断一个 $j$ 何时生效？

• 定义 $j$ 的‌生效时间‌为 $j + b[j]$
• 当遍历到 $i \ge$ 生效时间时，$j$ 就可以被后续所有位置使用

---

3. 桶优化

使用一个桶数组 bucket[x]，存储所有生效时间为 $x$ 的下标 $j$。

遍历 $i = 1 \to n$：

1. ‌收菜‌：将 bucket[i] 中所有 $j$ 的 $dp[j]$ 取出，更新 best = max(best, dp[j])
2. ‌计算‌：dp[i] = a[i] + best
3. ‌种菜‌：将 $i$ 放入 bucket[i + b[i]]（如果 $i + b[i] \le n$）

每个下标只会被放入桶一次、取出一次，总复杂度 $O(n)$。

---

4. 边界处理

当 $b[i] = 0$ 时，$i + b[i] = i$，会导致激活时机早于 $dp[i]$ 的计算，使 $dp[i]$ 的正确值无法传递。

根据题目条件 $p_{i+1} \ge p_i + b_{p_i}$ 且下标严格递增，当 $b[i] = 0$ 时，实际生效时间应为 $i + 1$。

因此统一处理为：生效时间 $t = i + \max(1, b[i])$。

---

代码实现

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

const int N = 2e5 + 5;
int a[N], b[N];
vector<int> bucket[N];
ll dp[N];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

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

    // 初始化桶
    for (int i = 1; i <= n; i++) {
        int t = i + max(1, b[i]);
        if (t <= n) bucket[t].push_back(i);
    }

    ll best = 0, ans = 0;
    for (int i = 1; i <= n; i++) {
        // 激活所有生效时间为 i 的下标
        for (int j : bucket[i]) {
            best = max(best, dp[j]);
        }
        dp[i] = best + a[i];
        ans = max(ans, dp[i]);
    }

    cout << ans << "\n";
    return 0;
}