2026年3月GESP6级选数题解

题目描述给定两个包含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​≤n1 ≤ i ≤ k 1\leq i\leq k1≤i≤kp i 1 ≥ p i b p i p_{i1}\geq p_ib_{p_i}pi1​≥pi​bpi​​1 ≤ i k 1\leq i k1≤ik。你需要在满足以上条件的前提下最大化∑ i 1 k a p i \sum_{i1}^k a_{p_i}∑i1k​api​​也即最大化数组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对应下标的整数之和的最大值。输入输出样例 #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 ≤ 10 3 2\leq n\leq 10^32≤n≤103。对于所有测试点保证2 ≤ n ≤ 10 5 2\leq n\leq 10^52≤n≤1050 ≤ a i ≤ 10 9 0\leq a_i\leq 10^90≤ai​≤1090 ≤ b i ≤ n 0\leq b_i\leq n0≤bi​≤n。思路解法他给你了三个数组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 [ p 1 , … , p k ] p[p_1,\dots,p_k]p[p1​,…,pk​]。他要让p pp满足以下条件{ 1 ≤ p i ≤ n 1 ≤ i ≤ k p i 1 ≥ p i b p i 1 ≤ i k \begin{cases} 1\leq p_i\leq n 1\leq i\leq k\\ p_{i1}\geq p_ib_{p_i} 1\leq i k\\ \end{cases}{1≤pi​≤npi1​≥pi​bpi​​​1≤i≤k1≤ik​把p pp的各个位置想象成并排的小房子且里面都装了安防系统在p i b p i − 1 p_i b_{p_i} -1pi​bpi​​−1以内的地方偷了会报警a aa是每家有多少钱我最多可以偷多少钱不触发报警系统分析到这里这就很像Leetcode的这道题这也告诉我们这道题是 dp。还有一个要注意的点dp要开l o n g l o n g long longlonglong不开见祖宗AC CODE:#includebits/stdc.husingnamespacestd;longlongdp[int(1e55)];longlonga[int(1e55)];longlongb[int(1e55)];intmain(){intn;cinn;for(inti1;in;i){cina[i];}for(inti1;in;i){cinb[i];}longlongans0;for(inti1;in;i){ansmax(ans,dp[i]a[i]);if(ib[i]n)dp[ib[i]]max(dp[ib[i]],dp[i]a[i]);dp[i1]max(dp[i1],dp[i]);}coutans;}详情