2026年6月GESP真题及题解（C++七级）：消消乐

2026年6月GESP真题及题解C七级消消乐题目描述给定一个由n nn个整数构成的数组a [ a 1 , … , a n ] a [a_1, \ldots, a_n]a[a1​,…,an​]。每次你可以对数组a aa进行以下操作直到数组a aa变为空指定a aa中的一个元素获得该元素两侧相邻元素之和的分数并将该元素从a aa中删去。特别地如果相邻元素不存在则该元素的值视为0 00。例如对于a [ 1 , 2 , 3 ] a [1, 2, 3]a[1,2,3]可以进行以下操作指定元素2 22获得分数1 3 1 313删去2 22后a [ 1 , 3 ] a [1, 3]a[1,3]指定元素1 11获得分数0 3 0 303删去1 11后a [ 3 ] a [3]a[3]指定元素3 33获得分数0 0 0 000删去3 33后a aa变为空。请问你能获得的分数总和最大是多少输入格式第一行一个正整数n nn表示数组长度。第二行n nn个非负整数a 1 , … , a n a_1, \ldots, a_na1​,…,an​表示数组a aa中的整数。输出格式输出一行一个整数表示能获得的最大分数总和。输入输出样例 1输入 16 1 6 3 2 9 1输出 155输入输出样例 2输入 25 3 1415 926 53 58输出 25771数据范围对于40 % 40\%40%的测试点保证1 ≤ n ≤ 50 1 \le n \le 501≤n≤500 ≤ a i ≤ 10 3 0 \le a_i \le 10^30≤ai​≤103。对于所有测试点保证1 ≤ n ≤ 100 1 \le n \le 1001≤n≤1000 ≤ a i ≤ 10 9 0 \le a_i \le 10^90≤ai​≤109。思路分析把删除过程反过来看一个元素最后被删除时它左右两边的元素都已经被删光了所以这一步得分只和区间左右边界有关。设dp[l][r]表示在区间[l, r]内左右两边各有一个“哨兵”元素a[l-1]和a[r1]始终保留的情况下删光区间内所有元素能获得的最大分数。如果哨兵不存在值视为0。枚举区间内最后被删除的元素k删k之前左右两个子区间[l, k-1]和[k1, r]已经被删光此时k的左右相邻元素就是两个哨兵a[l-1]和a[r1]所以这一步得分为a[l-1] a[r1]左右子区间互不影响可以独立求解。因此转移方程为dp[l][r] max( dp[l][k-1] dp[k1][r] a[l-1] a[r1] )其中k从l枚举到r。空区间得分为0边界a[0] a[n1] 0。最终答案为dp[1][n]。时间复杂度O ( n 3 ) O(n^3)O(n3)空间复杂度O ( n 2 ) O(n^2)O(n2)n 100足够。代码实现#includebits/stdc.husingnamespacestd;typedeflonglongll;constintN105;ll a[N],dp[N][N];// a:原数组dp:区间最大得分intmain(){intn;cinn;for(inti1;in;i)cina[i];a[0]a[n1]0;// 边界视为0for(intlen1;lenn;len){// 枚举区间长度for(intl1;llen-1n;l){intrllen-1;ll best0;for(intkl;kr;k){// k:区间内最后删除的元素ll curdp[l][k-1]dp[k1][r]a[l-1]a[r1];if(curbest)bestcur;}dp[l][r]best;}}coutdp[1][n];return0;}功能分析读入数组长度n和数组元素用区间动态规划计算删除所有元素能获得的最大分数转移时枚举区间内最后删除的元素合并左右子区间并加上最后一步得分各种学习资料助力大家一站式学习和提升#includebits/stdc.husingnamespacestd;intmain(){cout########## 一站式掌握信奥赛知识! ##########;cout############# 冲刺信奥赛拿奖! #############;cout###### 课程购买后永久学习不受限制! ######;return0;}【秘籍汇总】完整csp信奥赛C学习资料1、csp/信奥赛C完整信奥赛系列课程永久学习https://edu.csdn.net/lecturer/7901 点击跳转2、CSP信奥赛C竞赛拿奖视频课https://edu.csdn.net/course/detail/40437 点击跳转https://edu.csdn.net/course/detail/41081 点击跳转3、csp信奥赛高频考点知识详解及案例实践CSP信奥赛C动态规划https://blog.csdn.net/weixin_66461496/category_13096895.html点击跳转CSP信奥赛C标准模板库STLhttps://blog.csdn.net/weixin_66461496/category_13108077.html 点击跳转信奥赛C提高组csp-s知识详解及案例实践https://blog.csdn.net/weixin_66461496/category_13113932.html 点击跳转4、csp信奥赛冲刺一等奖有效刷题题解信奥赛C普及组CSP-J一等奖通关刷题题单及题解https://blog.csdn.net/weixin_66461496/category_12673810.html 点击跳转信奥赛C普及组csp-j初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12808781.html 点击跳转信奥赛C提高组csp-s初赛复赛真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13125089.html 点击跳转5、GESP C考级真题题解GESP(C 一级二级三级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12858102.html 点击跳转GESP(C 四级五级六级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_12869848.html 点击跳转GESP(C 七级八级)真题题解持续更新https://blog.csdn.net/weixin_66461496/category_13117178.html 点击跳转· 文末祝福 ·#includebits/stdc.husingnamespacestd;intmain(){cout跟着王老师一起学习信奥赛C;cout 成就更好的自己 ;cout csp信奥赛一等奖属于你! ;return0;}