文章目录202606 GESP 7 级第 2 题题面P17015 [GESP202606 七级] 消消乐题目描述输入格式输出格式输入输出样例 #1输入 #1输出 #1输入输出样例 #2输入 #2输出 #2说明/提示数据范围解END题外话202606 GESP 7 级第 2 题2026 年 06 月的这次 GESP 几乎是大放水。几乎所有级别的整体难度跟前两次相比是降低的。但是 7 级却出现了一点意外。也就是 7 级的第二题。网上爆出很多同学都不会做。当时我再带另一个比赛没有去细查什么情况。直到官方发布真题后我第一时间下载了 7 级试卷去看了看。然后我的第一反应是“这难道不是很模板的水题吗”然后仔细一想发现不对哦原来又是“超纲”。让我们来看下现在 7 级的考纲。知识内容知识目标数学库常用函数三角、对数、指数复杂动态规划二维动态规划、动态规划最值优化图的定义及遍历图论基本算法图的深度优先遍历、广度优先遍历、泛洪算法哈希表掌握图的定义与遍历相关算法掌握图论基本概念及基础算法能使用二维动态规划、动态规划最值优化的知识完成复杂的动态规划算法为什么我上面的超纲打引号因为考纲里的动态规划说得非常模糊。复杂动态规划能有多复杂二维动态规划是可以降到1维那种还是从3维降下来的所以说从网上的现象看来目前大多数机构或者课程是很少有讲过本次的这种题型也就是区间DP。其实区间DP是在各种专业竞赛的书籍和题单里必定会出现的一个常见知识点但是我不知道为什么这类机构不讲这个。也许是。。。题面P17015 GESP202606 七级 消消乐 - 洛谷P17015 [GESP202606 七级] 消消乐题目描述给定一个由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。解#includebits/stdc.husingnamespacestd;constintM101e2;intarr[M];intdp[M][M];intmain(){intn;cinn;for(inti1;in;i1){cinarr[i];}// 区间 dp// 枚举区间长度for(intlen1;lenn;len1){// 枚举区间的左右端点for(inti1,jilen-1;jn;i1,j1){// 划分区域 [i, k-1] [k] [k1, j]for(intki;kj;k1){dp[i][j]max(dp[i][j]// 松弛,(dp[i][k-1]dp[k1][j])// 两边的 dp(arr[i-1]0arr[j1])// 区间外的两个测题意得贡献);}}}coutdp[1][n]endl;return0;}类似题leetcode - 312. 戳气球hdu - 5115 Dire WolfEND题外话hdu - 5115 Dire Wolf 是 2014 ACM/ICPC 亚洲区北京站的一道真题。在 hdu 上是有收录的。我想看看在洛谷上有没有收录然后我在洛谷上搜了搜没有。然后我去让 DeepSeek 帮我查查然后 DeepSeek 告诉我没有。但让我看到了另一个东西。然后我尝试点开看一下发现 404 了。其实这篇是我在 2022 年的时候写在 CSDN 上的一篇 区间DP 的博客只是估计又被哪个网站收编了。然后这个网站的这个节点 404 了。然后导致我这个作者都看不了了。原文如下(区间dp) (经典例题) 石子合并 -CSDN博客