洛谷 P15800：[GESP202603 六级] 选数 ← 动态规划

【题目来源】https://www.luogu.com.cn/problem/P15800【题目描述】【输入格式】第一行一个正整数表示数组长度。第二行n 个正整数 a1, a2, …, an表示数组 a。第三行n 个正整数 b1, b2, …, bn表示数组 b。【输出格式】一行一个整数表示在满足下标条件的前提下数组 a 对应下标的整数之和的最大值。【输入样例】61 1 4 5 1 41 2 3 2 1 0​​​​​​​【输出样例】11【数据范围】对于 40% 的测试点保证 2≤n≤10^3。对于所有测试点保证 2≤n≤10^50≤ai≤10^90≤bi≤n。【算法分析】● 闫氏 DP 分析法https://www.bilibili.com/video/BV1X741127ZM● 最后一步法https://www.bilibili.com/video/BV1xb411e7ww● 解题思路来源于https://mp.weixin.qq.com/s/MzuV2CmidkGD5I-EMGS28A这是一个典型的带跳跃限制的动态规划问题。如果我们当前选择位置 i那么下一个可选择的位置必须满足 j≥ib[i]。因此可以从 i 跳到区间 [ib[i], n]。1状态定义设 f[i] 表示当第一个选择的位置是 i 时能够获得的最大收益。2状态转移如果选择了 i下一步可以选任意 j∈[ib[i], n]。于是f[i]a[i]max(f[j]) 其中 j≥ib[i]如果 ib[i]n说明后面不能再选。此时有 f[i]a[i]。3优化直接枚举 j 会变成 O(n²)。我们可以维护一个后缀最大值数组 mx[i] max(f[i], f[i1], ..., f[n])。这样就能 O(1) 得到 max(f[j])当 j≥ib[i]mx[ib[i]] 时。于是转移方程优化为当 ib[i]n时f[i]a[i]mx[ib[i]]。否则f[i]a[i]。4最终答案因为可以从任意位置开始答案就是 max(f[1], f[2], ..., f[n])。复杂度分析DP 计算 O(n)空间复杂度 O(n)。整体复杂度 O(n)完美通过。【算法代码】#include bits/stdc.h using namespace std; typedef long long LL; const int N1e55; int a[N],b[N]; LL f[N],ans; int n; int main() { ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cinn; for(int i1; in; i) cina[i]; for(int i1; in; i) cinb[i]; for(int i1; in; i) { ansmax(ans,f[i]a[i]); if(ib[i]n) { f[ib[i]]max(f[ib[i]],f[i]a[i]); } f[i1]max(f[i1],f[i]); } coutans; return 0; } /* in: 6 1 1 4 5 1 4 1 2 3 2 1 0 out: 11 */【参考文献】https://gesp.ccf.org.cn/101/attach/1734457386074144.pdfhttps://blog.csdn.net/hnjzsyjyj/article/details/113549272https://mp.weixin.qq.com/s/MzuV2CmidkGD5I-EMGS28Ahttps://mp.weixin.qq.com/s/xPLBl-FiJOvgF83-lqbGTA