G6021 [GESP202603 六级] 选数 题解

知识点：动态规划、序列选择、跳跃状态。

解题思路

令dp[i]为从i开始能取的最大和。不选i取dp[i+1]；选i则加a[i]并跳到至少i+b[i]，倒序取两者最大。

为什么正确

任何合法方案按是否选当前下标分两类，选中后所有后继必须满足跳跃下界，后缀最优即可独立衔接。

易错点

下标必须严格增加，代码用max(1,b[i])保护推进；越过末尾映射到空后缀。

复杂度

时间O(n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin>>n;
    vector<long long>a(n);
    vector<int>b(n);
    for(auto &x:a)cin>>x;
    for(auto &x:b)cin>>x;
    vector<long long>dp(n+1);
    for(int i=n-1;i>=0;i--)dp[i]=max(dp[i+1],a[i]+dp[min(n,i+max(1,b[i]))]);
    cout<<dp[0];
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用12个自行生成的测试点。