EXY-PG-0047
第 10 题
选数
题目描述
给定两个包含 n 个整数的数组 $a=[a_1,…,a_n]$ 与 $b=[b_1,…,b_n]$。你需要指定若干下标 $p_1<⋯<p_k(1≤k≤n)$ 使得以下条件成立：
- $1≤p_i≤n（1≤i≤k）$；
- $p_{i+1}≥p_i+b_{p_i} (1≤i<k)$。
你需要在满足以上条件的前提下最大化 $ \sum_{i=1}^k a_{p_i}$，也即最大化数组 a 对应下标的整数之和。
输入格式
第一行，一个正整数 n，表示数组长度。
第二行，n 个正整数 $a_1,a_2,…,a_n$，表示数组 a。
第三行，n 个正整数 $b_1,b_2,…,b_n$，表示数组 b。
输出格式
一行，一个整数，表示在满足下标条件的前提下，数组 a 对应下标的整数之和的最大值。
样例说明
样例 1
输入：
4
1 2 3 4
3 3 1 1
输出：
7样例 2
输入：
6
1 1 4 5 1 4
1 2 3 2 1 0
输出：
11数据范围
对于 40% 的测试点，保证 $2≤n≤10^3$。
对于所有测试点，保证 $2≤n≤10^5，0≤a_i≤10^9，0≤b_i≤n$。
语言：
C++
GESP真题
六级
2026.3
编程题号：
1
当前页显示 10 - 10
，共 50 道编程题