题解在最下方

P15800 [GESP202603 六级] 选数

题目背景

对应的选择、判断题：https://ti.luogu.com.cn/problemset/1210

题目描述

给定两个包含 \(n\) 个整数的数组 \(a=[a_1,\dots,a_n]\) 与 \(b=[b_1,\dots,b_n]\)。你需要指定若干下标 \(p_1\lt \cdots\lt p_k\)（\(1\leq k\leq n\)）使得以下条件成立：

• \(1\leq p_i\leq n\)（\(1\leq i\leq k\)）；
• \(p_{i+1}\geq p_i+b_{p_i}\)（\(1\leq i< k\)）。

你需要在满足以上条件的前提下最大化 \(\sum_{i=1}^k a_{p_i}\)，也即最大化数组 \(a\) 对应下标的整数之和。

输入格式

第一行，一个正整数 \(n\)，表示数组长度。

第二行，\(n\) 个正整数 \(a_1,a_2,\dots,a_n\)，表示数组 \(a\)。

第三行，\(n\) 个正整数 \(b_1,b_2,\dots,b_n\)，表示数组 \(b\)。

输出格式

一行，一个整数，表示在满足下标条件的前提下，数组 \(a\) 对应下标的整数之和的最大值。

输入输出样例 #1

输入 #1

4
1 2 3 4
3 3 1 1

输出 #1

7

输入输出样例 #2

输入 #2

6
1 1 4 5 1 4
1 2 3 2 1 0

输出 #2

11

说明/提示

对于 \(40\%\) 的测试点，保证 \(2\leq n\leq 10^3\)。

对于所有测试点，保证 \(2\leq n\leq 10^5\)，\(0\leq a_i\leq 10^9\)，\(0\leq b_i\leq n\)。

题解

题目大意

有一个长度为 \(n\) 的两个数组 \(a,b\)，你可以在其中**选择一些数**。如果你**选择了下标为 \(i\) 的这个数，则可以加上 \(a_i\) 的值**，**但选下一个数只能在下标 \(\geq b_i+i\)。**也可以不再选择其他的数。求可以得到的最大价值。

解题思路

考虑 DP。

根据题目可以得知这道题应该倒序进行 dp。

dp题目解题步骤：

• 状态
• 转移
• 初始化

\(dp_i\) 表示从 \(i \sim n\) 可以得到的最大价值。（状态）

【重点】其中有两种情况，分别进行分类讨论（转移）：

• 不选 \(i\) 这个数：从上一个状态直接转移过来，则状态转移方程为 \(dp_i= dp_{i+1}\)
• 选 \(i\) 这个数：要注意我们只能选 \(b_i+i\) 之后的元素，所以我们就应该为当前这个数的价值加上后方的 dp 的最大值可以得到。即 \(dp_i=a_i+dp_{i+b_i}\)。其中注意，由于我们选取的小标一定是保证严格小于的，所以如果 \(b_i=0\)，就说明 \(p_i \le p_i+1\)，这很显然是不合理的。所以这里我们需要特判如果为 \(0\)，则我们就取 \(1\)。所以状态转移方程变为 \(dp_i=a_i+dp_{i+max(b_i,1)}\)。

这就是对于每个状态的两种情况的转移方式。由于我们要求最大的，则需要把两种情况的转移式进行合并求最大值，也就可以得到最终的状态转移方程：

\[dp_i=max(dp_{i+1},a_i+dp_{i+max(b_i,1)})\]

初始化本题目有两种情况，就算 dp 初始为 \(0\)，第一种情况也会加上 \(a_i\)。故不需要初始化。

题目要求我们求整个数组可以得到的最大价值，也就是 \(1 \sim n\)。对应 dp 中存值为 \(dp_1\)，因此输出 \(dp_1\) 即可。

注意开 long long。

AC Code

#include<bits/stdc++.h>
using namespace std;
using ll=long long;
const int N=2e6+10;
ll n,a[N],b[N],dp[N];
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=n;i>=1;i--) dp[i]=max(dp[i+1],a[i]+dp[i+max(b[i],1LL)]);
    cout<<dp[1];
    return 0;
}