基于Springboot高校心理咨询管理系统【附源码+文档】
2026/10/15 2:43:27
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 + 31+3，删去2 22后a = [ 1 , 3 ] a = [1, 3]a=[1,3]；
- 指定元素1 11，获得分数0 + 3 0 + 30+3，删去1 11后a = [ 3 ] a = [3]a=[3]；
- 指定元素3 33，获得分数0 + 0 0 + 00+0，删去3 33后a aa变为空。
请问你能获得的分数总和最大是多少？
输入格式
第一行，一个正整数n nn，表示数组长度。
第二行，n nn个非负整数a 1 , … , a n a_1, \ldots, a_na1,…,an，表示数组a aa中的整数。
输出格式
输出一行，一个整数，表示能获得的最大分数总和。
输入输出样例 1
输入 1
6 1 6 3 2 9 1输出 1
55输入输出样例 2
输入 2
5 3 1415 926 53 58输出 2
5771数据范围
对于40 % 40\%40%的测试点，保证1 ≤ n ≤ 50 1 \le n \le 501≤n≤50，0 ≤ a i ≤ 10 3 0 \le a_i \le 10^30≤ai≤103。
对于所有测试点，保证1 ≤ n ≤ 100 1 \le n \le 1001≤n≤100，0 ≤ a i ≤ 10 9 0 \le a_i \le 10^90≤ai≤109。
思路分析
把删除过程反过来看：一个元素最后被删除时，它左右两边的元素都已经被删光了，所以这一步得分只和区间左右边界有关。
设dp[l][r]表示：在区间[l, r]内，左右两边各有一个“哨兵”元素a[l-1]和a[r+1]始终保留的情况下，删光区间内所有元素能获得的最大分数。
如果哨兵不存在，值视为0。
枚举区间内最后被删除的元素k：
- 删
k之前，左右两个子区间[l, k-1]和[k+1, r]已经被删光； - 此时
k的左右相邻元素就是两个哨兵a[l-1]和a[r+1]，所以这一步得分为a[l-1] + a[r+1]； - 左右子区间互不影响，可以独立求解。
因此转移方程为：
dp[l][r] = max( dp[l][k-1] + dp[k+1][r] + a[l-1] + a[r+1] )其中k从l枚举到r。
空区间得分为0，边界a[0] = a[n+1] = 0。
最终答案为dp[1][n]。
时间复杂度O ( n 3 ) O(n^3)O(n3)，空间复杂度O ( n 2 ) O(n^2)O(n2)，n <= 100足够。
代码实现
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;constintN=105;ll a[N],dp[N][N];// a:原数组，dp:区间最大得分intmain(){intn;cin>>n;for(inti=1;i<=n;i++)cin>>a[i];a[0]=a[n+1]=0;// 边界视为0for(intlen=1;len<=n;len++){// 枚举区间长度for(intl=1;l+len-1<=n;l++){intr=l+len-1;ll best=0;for(intk=l;k<=r;k++){// k:区间内最后删除的元素ll cur=dp[l][k-1]+dp[k+1][r]+a[l-1]+a[r+1];if(cur>best)best=cur;}dp[l][r]=best;}}cout<<dp[1][n];return0;}功能分析
- 读入数组长度
n和数组元素； - 用区间动态规划计算删除所有元素能获得的最大分数；
- 转移时枚举区间内最后删除的元素，合并左右子区间，并加上最后一步得分；
各种学习资料，助力大家一站式学习和提升！！！
#include<bits/stdc++.h>usingnamespacestd;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++标准模板库STL：
https://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 点击跳转
· 文末祝福 ·
#include<bits/stdc++.h>usingnamespacestd;intmain(){cout<<"跟着王老师一起学习信奥赛C++";cout<<" 成就更好的自己！ ";cout<<" csp信奥赛一等奖属于你! ";return0;}