选数题解

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
以下为代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
typedef long long ll;
ll a[N],b[N],n,dp[N],ans;
int main(){
    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++){
        ans=max(ans,dp[i]+a[i]);
        if(i+b[i]<=n){
            dp[i+b[i]]=max(dp[i+b[i]],dp[i]+a[i]);
        }
        dp[i+1]=max(dp[i],dp[i+1]);
    }
    cout<<ans;
    return 0;
}

依旧题解