当前位置：首页 > news >正文

题解：洛谷 P15800 [GESP202603 六级] 选数

news 2026/5/7 13:30:44

本文分享的必刷题目是从蓝桥云课、洛谷、AcWing等知名刷题平台精心挑选而来，并结合各平台提供的算法标签和难度等级进行了系统分类。题目涵盖了从基础到进阶的多种算法和数据结构，旨在为不同阶段的编程学习者提供一条清晰、平稳的学习提升路径。

欢迎大家订阅我的专栏：算法题解：C++与Python实现！

附上汇总贴：算法竞赛备考冲刺必刷题（C++） | 汇总

【题目来源】

洛谷：[P15800 GESP202603 六级] 选数 - 洛谷

【题目描述】

给定两个包含n nn个整数的数组a = [ a 1 , … , a n ] a=[a_1,\dots,a_n]a=[a1,…,an]与b = [ b 1 , … , b n ] b=[b_1,\dots,b_n]b=[b1,…,bn]。你需要指定若干下标p 1 < ⋯ < p k p_1\lt \cdots\lt p_kp1<⋯<pk（1 ≤ k ≤ n 1\leq k\leq n1≤k≤n）使得以下条件成立：

1 ≤ p i ≤ n 1\leq p_i\leq n1≤pi≤n（1 ≤ i ≤ k 1\leq i\leq k1≤i≤k）；
p i + 1 ≥ p i + b p i p_{i+1}\geq p_i+b_{p_i}pi+1≥pi+bpi（1 ≤ i < k 1\leq i< k1≤i<k）。

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

【输入】

第一行，一个正整数n nn，表示数组长度。

第二行，n nn个正整数a 1 , a 2 , … , a n a_1,a_2,\dots,a_na1,a2,…,an，表示数组a aa。

第三行，n nn个正整数b 1 , b 2 , … , b n b_1,b_2,\dots,b_nb1,b2,…,bn，表示数组b bb。

【输出】

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

【输入样例】

4 1 2 3 4 3 3 1 1

【输出样例】

【算法标签】

#普及# #线性DP-一维#

【代码详解】

// 40分版本#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=100005;intn,a[N],b[N],ans;// dp[i] 表示以第 i 个活动结尾时，能获得的最大价值intdp[N];intlen=0;signedmain(){cin>>n;for(inti=1;i<=n;i++){cin>>a[i];}for(inti=1;i<=n;i++){cin>>b[i];}for(inti=1;i<=n;i++){// 初始化：只选择第 i 个活动dp[i]=a[i];// 考虑在 i 之前的活动 jfor(intj=1;j<i;j++){// 检查活动 j 结束后是否可以安排活动 iif(i>=j+b[j]){// 如果可以，则尝试从活动 j 转移到活动 idp[i]=max(dp[i],dp[j]+a[i]);}}}// 找到所有 dp[i] 中的最大值for(inti=1;i<=n;i++){ans=max(ans,dp[i]);}cout<<ans<<endl;return0;}

// 100分版本#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintN=100005;intn,a[N],b[N];// dp[i]: 到时间i为止能获得的最大收益（不包含在时间i开始的任务）intdp[N];signedmain(){cin>>n;for(inti=1;i<=n;i++){cin>>a[i];}for(inti=1;i<=n;i++){cin>>b[i];}intans=0;for(inti=1;i<=n;i++){// 情况1: 在时间i开始执行任务i// 收益 = 到时间i为止的最大收益 + 任务i的收益ans=max(ans,dp[i]+a[i]);// 如果执行任务iintfinish_time=i+b[i];if(finish_time<=n){// 在任务i结束时更新收益dp[finish_time]=max(dp[finish_time],dp[i]+a[i]);}// 情况2: 在时间i不执行任何任务// 收益延续到下一个时间点dp[i+1]=max(dp[i+1],dp[i]);}// 注意：最终答案不一定是dp[n]，因为可能在n时刻之前就已经得到了最大收益// 我们已经在循环中通过ans记录了所有可能的最大值cout<<ans<<endl;return0;}