A20881. 选数
填空题
困难
知识点
题目描述
选数
题目描述
给定两个包含n个整数的数组a=[a1,...,an]与b=(b1,...,bn]。你需要指定若干下标 P1<...<Pk (1≤k≤n)使得以下条件成立:
1≤pi≤n (1≤i≤k);
Pi+1≥pi+bpi (1≤i<k)。
你需要在满足以上条件的前提下最大化∑ki=1 api，也即最大化数组a对应下标的整数之和。
输入格式
第一行，一个正整数n，表示数组长度。
第二行，n个正整数a1,a2,...,an，表示数组a。
第三行，n个正整数b1,b2,...,bn，表示数组b。
输出格式
一行，一个整数，表示在满足下标条件的前提下，数组a对应下标的整数之和的最大值。
样例
输入样例 1
4
1 2 3 4
3 3 1 1输出样例 1
7输入样例 2
6
1 1 4 5 1 4
1 2 3 2 1 0输出样例 2
11数据范围
对于40%的测试点，保证2≤n≤103。
对于所有测试点，保证2≤n≤105,0≤ai≤109，0≤bi≤n.
参考答案
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e5 + 5;
int n;
int a[N], b[N];
long long f[N], ans;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++)
scanf("%d", &a[i]);
for (int i = 1; i <= n; i++)
scanf("%d", &b[i]);
for (int i = 1; i <= n; i++) {
ans = max(ans, f[i] + a[i]);
if (i + b[i] <= n)
f[i + b[i]] = max(f[i + b[i]], f[i] + a[i]);
f[i + 1] = max(f[i + 1], f[i]);
}
printf("%lld\n", ans);
return 0;
}
上一题
下一题