DP
2026-08-26 16:41:46
发布于:广东
3阅读
0回复
0点赞
#include<bits/stdc++.h> // 万能头文件,包含所有标准库
using namespace std;
using ll = long long; // 定义 ll 为 long long 类型,防止整数溢出
const ll N = 2e5+10; // 最大数组长度,2e5+10 = 200010
ll n, a[N], b[N]; // 全局数组,自动初始化为0
ll dp[N], suf[N]; // dp: 必须从i开始选的最大值
// suf: 从i或之后开始选的最大值
int main() {
// 读入数据
cin >> n; // 读入数组长度
for(int i = 1; i <= n; i++) cin >> a[i]; // 读入a数组(分值)
for(int i = 1; i <= n; i++) cin >> b[i]; // 读入b数组(跳跃距离)
// 核心DP:从后往前遍历
for(int i = n; i >= 1; i--) {
// 关键修正:如果 b[i] = 0,至少要跳到下一个位置
// 因为选择的下标必须不同,所以至少要前进1步
// max(1LL, b[i]) 确保最小跳跃距离为1
int nxt = i + max(1LL, b[i]);
// 情况1:跳出了数组范围
if(nxt > n) {
// 选了i之后不能继续选了,只能得a[i]分
dp[i] = a[i];
}
// 情况2:还可以继续跳
else {
// 必须选i:得a[i]分
// 然后从nxt或之后选最优的继续:suf[nxt]表示从nxt开始的最佳得分
dp[i] = a[i] + suf[nxt];
}
// 更新后缀最大值
// suf[i] = max(不选i, 选i)
// suf[i+1]:从i+1或之后开始选(不选i)
// dp[i]:必须从i开始选(选i)
suf[i] = max(suf[i+1], dp[i]);
}
// 输出答案:从1或之后开始选的最大值
// 因为可以选择任意起点,所以答案是suf[1]
cout << suf[1] << endl;
return 0;
}
这里空空如也


有帮助,赞一个