CCF-GESP计算机学会等级考试2026年3月六级C++T1 选数

P15800 [GESP202603 六级] 选数题目描述给定两个包含nnn个整数的数组a[a1,…,an]a[a_1,\dots,a_n]a[a1​,…,an​]与b[b1,…,bn]b[b_1,\dots,b_n]b[b1​,…,bn​]。你需要指定若干下标p1⋯pkp_1\lt \cdots\lt p_kp1​⋯pk​1≤k≤n1\leq k\leq n1≤k≤n使得以下条件成立1≤pi≤n1\leq p_i\leq n1≤pi​≤n1≤i≤k1\leq i\leq k1≤i≤kpi1≥pibpip_{i1}\geq p_ib_{p_i}pi1​≥pi​bpi​​1≤ik1\leq i k1≤ik。你需要在满足以上条件的前提下最大化∑i1kapk\sum_{i1}^k a_{p_k}∑i1k​apk​​也即最大化数组aaa对应下标的整数之和。输入格式第一行一个正整数nnn表示数组长度。第二行nnn个正整数a1,a2,…,ana_1,a_2,\dots,a_na1​,a2​,…,an​表示数组aaa。第三行nnn个正整数b1,b2,…,bnb_1,b_2,\dots,b_nb1​,b2​,…,bn​表示数组bbb。输出格式一行一个整数表示在满足下标条件的前提下数组aaa对应下标的整数之和的最大值。输入输出样例 #1输入 #14 1 2 3 4 3 3 1 1输出 #17输入输出样例 #2输入 #26 1 1 4 5 1 4 1 2 3 2 1 0输出 #211说明/提示对于40%40\%40%的测试点保证2≤n≤1032\leq n\leq 10^32≤n≤103。对于所有测试点保证2≤n≤1052\leq n\leq 10^52≤n≤1050≤ai≤1090\leq a_i\leq 10^90≤ai​≤1090≤bi≤n0\leq b_i\leq n0≤bi​≤n。题解40%的暴力动态规划核心思路暴力动态规划这个解法是最直观的动态规划思路没有任何优化完全遵循题目要求的条件状态定义dp[i] 表示 “选择第 i 个元素作为最后一个选中元素时能获得的最大和”。初始状态dp[i] a[i]只选第 i 个元素不选任何前驱。状态转移对于每个 i遍历所有 j i若满足 j b[j] ≤ i选 j 后可以选 i则 dp[i] max(dp[i], dp[j] a[i])选 j 的最优和 选 i 的收益。最终答案所有 dp[i] 中的最大值因为最后一个选中的元素可以是任意位置。时间复杂度为O(n²)。详见代码#includebits/stdc.husingnamespacestd;intn;inta[100005];intb[100005];longlongdp[100005];//dp[i]表示选择第i个元素时能获得的最大和longlongans0;// 全局最大和最终答案intmain(){cinn;for(inti1;in;i){cina[i];}for(inti1;in;i){cinb[i];}// 第一层循环枚举选中的最后一个元素ifor(inti1;in;i){// 初始状态只选第i个元素dp[i]a[i];// 第二层循环枚举i之前的所有可能前驱jfor(intj1;ji;j){// 满足条件j b[j] ≤ ij的下一个位置至少是iif(jb[j]i){// 状态转移选j后再选i取最大值dp[i]max(dp[i],dp[j]a[i]);}}// 更新全局最大值ansmax(ans,dp[i]);}coutansendl;return0;}正解C代码#includebits/stdc.husingnamespacestd;intn;inta[100005];intb[100005];longlongf[100005];//f[i]表示处理到第i个位置时能继承的最大和即选i之前的最优解longlongans0;// 全局最大和最终答案intmain(){cinn;for(inti1;in;i){cina[i];}for(inti1;in;i){cinb[i];}// 线性遍历仅一次循环O(n)时间复杂度for(inti1;in;i){// 1. 选第i个元素时的最大和 继承的最优解 a[i]更新全局最大值ansmax(ans,f[i]a[i]);// 2. 标记后继位置选i后下一个可选位置是ib[i]将当前和传递过去intnext_posib[i];//下一个可行的位置if(next_posn){// 仅当后继位置在范围内时更新f[next_pos]max(f[next_pos],f[i]a[i]);}// 3. 懒更新前缀最大值将当前位置的最优解传递给下一个位置// 保证f[i1]始终是1~i位置能继承的最大和避免重复计算f[i1]max(f[i1],f[i]);}coutansendl;return0;}二、详细题解1. 核心思路这道题的关键是通过动态规划前缀最大值懒传递将原本需要二分优化的O(n log n)解法优化为纯线性O(n)状态定义f[i]表示“处理到第i个位置时能继承的最大和”即所有满足j b[j] ≤ i的j对应的最优解之和。核心操作选第i个元素当前和为f[i] a[i]更新全局最大值。标记后继选i后下一个可选位置是i b[i]将当前和传递到该位置。懒更新将f[i]当前最优解传递给f[i1]保证后续位置能继承到前面的最优解。2. 关键逻辑拆解代码行作用说明ans max(ans, f[i] a[i])计算选第i个元素的最大和并更新全局答案。f[i]是选i之前的最优解加a[i]就是选i的总收益。f[next_pos] max(f[next_pos], f[i] a[i])选i后下一个可选位置是i b[i]因此该位置能继承选i后的总收益取最大值避免覆盖更优解。f[i1] max(f[i1], f[i])懒更新前缀最大值如果i1位置没有被标记过即没有前驱选它则继承i位置的最优解保证f数组始终存储到当前位置为止的最大可继承和。3. 样例验证以样例1为例输入4 1 2 3 4 3 3 1 1执行过程if[i]选i的和(f[i]a[i])ans更新next_pos(ib[i])f[next_pos]更新f[i1]更新100111134f[4] max(0,1)1f[2]max(0,0)0200222235超界无f[3]max(0,0)0300333314f[4] max(1,3)3f[4]max(3,0)3433477415超界无f[5]max(0,3)3最终ans7与样例输出一致。4. 时间/空间复杂度分析时间复杂度仅一次for循环遍历1~n所有操作都是O(1)总复杂度为O(n)。空间复杂度使用了三个数组a、b、f空间复杂度为O(n)可优化为O(n)无法进一步优化因为需要存储每个位置的状态。5. 边界条件处理当i b[i] n时不更新f数组因为后继位置超出范围没有下一个可选元素。数组开n2位避免i1或ib[i]越界如in时i1n1。使用long long类型a[i]最大为1e9n最大为1e5总和可达1e14超出int范围int最大约2e9。三、总结该解法的核心是前缀最大值懒传递通过f[i1] max(f[i1], f[i])保证f数组始终存储到当前位置的最优可继承和避免了二分查找。标记后继位置的操作f[next_pos] max(...)确保了选i后下一个可选位置能继承当前的最优解。线性时间复杂度O(n)是本题的最优解在n1e5时运行效率远高于O(n log n)的二分解法。这个解法既满足题目要求又兼顾了代码的简洁性和效率是GESP六级选数问题的最优解法。