OK，我又来了，话不多数，进入正题 首先，这一题有两个约束条件 1 :1 ≤ pi ≤ n(1 ≤ i ≤ k) 2 :pi+1 ≥ pi + bpi(1 ≤ i ≤ k) 求在满足下标条件的前提下，数组 a 对应下标的整数之和的最大值 那么想都不用想,估计又是我们最爱的动态规划 先确定dp[i]表示什么 在处理完前i-1个位置，达到i时，之前的最大收益（dp[i]不包含a[i]，毕竟是是刚到达时的最大收益） 然后推动态转移方程 先"翻译"一下这两个约束条件 1:1 ≤ i ≤ n 2:j ≥ i + b[i] 第一个没什么好说 但是第二个，就有的说了 对于dp[i]的值，有两种可能 1.选择位置 i 如果我们决定在 i 拿走 a[i] ，那么收益就是dp[i]+a[i] 由2可知，下一个可以选的最近位置就在 i+b[i] （取等号） 那么dp[i+b[i]]就出来了 dp[i+b[i]]=max(dp[i+b[i]],dp[i]+a[i]) 2.不选择位置 i 如果对于a[i]我们不要，那就吧当前的收益递给下一个 dp[i+1]=max(dp[i+1],dp[i]) 结束了吗？NO，NO，NO 我们要求的是什么？再去看一眼！ 所以，在循环开始时，设一个ans存最大的dp[i]+a[i] 结合数据大小，这题开long long 以下为代码 依旧题解

这道题我用的倒推的方法 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 题目大意 给定两个长度为 nnn 的数组 aaa 和 bbb，你需要选择一个下标序列 p1<p2<⋯<pkp_1 < p_2 < \dots < p_kp1 <p2 <⋯<pk ，满足： * pi+1≥pi+bpip_{i+1} \ge p_i + b_{p_i}pi+1 ≥pi +bpi 求 ∑api\sum a_{p_i}∑api 的最大值。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 思路分析 1. 暴力 DP 定义 dp[i]dp[i]dp[i] 表示以第 iii 个位置作为最后一个选择时，能获得的最大金币数。 转移方程： dp[i]=a[i]+max⁡j<i, j+b[j]≤idp[j]dp[i] = a[i] + \max_{j < i,\ j + b[j] \le i} dp[j] dp[i]=a[i]+j<i, j+b[j]≤imax dp[j] 最终答案： ans=max⁡1≤i≤ndp[i]ans = \max_{1 \le i \le n} dp[i] ans=1≤i≤nmax dp[i] 直接枚举所有 jjj 的复杂度是 O(n)O(n)O(n)，会超时。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 2. 优化思路 观察转移条件 j+b[j]≤ij + b[j] \le ij+b[j]≤i： * 随着 iii 的增大，满足条件的 jjj 只会增加，不会减少 * 我们可以动态维护一个变量 best，表示‌当前所有已生效的 dp[j]dp[j]dp[j] 的最大值‌ 关键问题：如何判断一个 jjj 何时生效？ * 定义 jjj 的‌生效时间‌为 j+b[j]j + b[j]j+b[j] * 当遍历到 i≥i \gei≥ 生效时间时，jjj 就可以被后续所有位置使用 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 3. 桶优化 使用一个桶数组 bucket[x]，存储所有生效时间为 xxx 的下标 jjj。 遍历 i=1→ni = 1 \to ni=1→n： 1. ‌收菜‌：将 bucket[i] 中所有 jjj 的 dp[j]dp[j]dp[j] 取出，更新 best = max(best, dp[j]) 2. ‌计算‌：dp[i] = a[i] + best 3. ‌种菜‌：将 iii 放入 bucket[i + b[i]]（如果 i+b[i]≤ni + b[i] \le ni+b[i]≤n） 每个下标只会被放入桶一次、取出一次，总复杂度 O(n)O(n)O(n)。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 4. 边界处理 当 b[i]=0b[i] = 0b[i]=0 时，i+b[i]=ii + b[i] = ii+b[i]=i，会导致激活时机早于 dp[i]dp[i]dp[i] 的计算，使 dp[i]dp[i]dp[i] 的正确值无法传递。 根据题目条件 pi+1≥pi+bpip_{i+1} \ge p_i + b_{p_i}pi+1 ≥pi +bpi 且下标严格递增，当 b[i]=0b[i] = 0b[i]=0 时，实际生效时间应为 i+1i + 1i+1。 因此统一处理为：生效时间 t=i+max⁡(1,b[i])t = i + \max(1, b[i])t=i+max(1,b[i])。 ------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------ 代码实现