这道GESP 七级 2026 年 6 月编程题第二题《消消乐》，如果按照考试难度来评价，我认为：
⭐⭐⭐⭐⭐
这是本套试卷中，最难的一题。
很多同学看到题目后会想到：
贪心？
模拟？
链表删除？
区间DP？
事实上：
这是一道非常经典的区间DP题。
而且它和很多NOIP、CSP中的经典题：
戳气球
石子合并
矩阵连乘
都有相同的思想。
第一幕：神秘的消消乐游戏
1、假设有一排数字：
1 6 3 2 9 1（1）题目说：
每次选一个数字删掉。
获得：
左邻居 + 右邻居的分数。
（2）如果不存在邻居：
算02、例如：
1 6 3（1）删除6：
获得
1+3=4（2）然后变成：
1 3继续删。
（3）最后删光。
（4）问：
怎样删除才能获得最大总分？
第二幕：为什么贪心不行？
1、有的同学第一反应：
每次删当前收益最大的。
例如：
1 6 3 2 9 1先删2：
获得
3+9=12看起来不错。
但这样做以后，
后面的结构全部改变了。
2、这就是本题最大的特点：
删除一个元素，会影响后面所有元素的邻接关系。
因此：
当前最优 ≠ 整体最优贪心失效。
第三幕：换一个角度思考
1、这是区间DP最经典的思维转换。
很多同学习惯：
第一个删谁？ 第二个删谁？ 第三个删谁？越来越乱。
2、高手会反过来想：
最后一个删谁？
这一下问题就简单了。
3、假设区间：
[l ...... r]里面最后删掉的是：
k例如：
1 6 3 2 9 1最后删的是：
2那么意味着：
在删2之前：
左边全部删光 右边全部删光已经完成。
于是：
删2时，
它的邻居是谁？
神奇的事情发生了。
第四幕：定义状态
1、状态：
f[l][r]表示：
删除区间 [l,r] 中所有数字能够获得的最大分数。
2、例如：
f[3][5]表示：
a[3] a[4] a[5]全部删掉的最大收益。
第五幕：状态转移
1、这是整题最核心的地方。
（1）假设：
区间：
[l......r]最后删的是：
k（2）那么：
[l......k-1]先删完。
获得：
f[l][k-1]（3）然后：
[k+1......r]也删完。
获得：
f[k+1][r]（4）最后轮到：
k被删。
此时：
区间内部已经空了。
只剩边界了。
（5）于是：
k获得的分数就是：
a[l-1] + a[r+1]2、所以：
转移公式：
f[l][r] = max( f[l][r], f[l][k-1] + f[k+1][r] + a[l-1] + a[r+1] );这是本题的核心。
第六幕：为什么是 a[l-1] 和 a[r+1]？
1、这是本题中，需要重点理解的地方。
很多同学会问：
为什么不是 a[k-1] 和 a[k+1]？
2、因为：
我们讨论的是：
最后删除k的时候。
3、此时：
[l,r]内部已经全部删光。
4、例如：
8 1 6 3 2 7（1）考虑区间：
[2,5]即：
1 6 3 2全部删除。
（2）如果：
最后删的是：
3（3）那么：
1 6 2都已经没了。
（4）此时3两边是谁？
不是：
6 2因为它们已经消失。
（5）而是：
区间外面的：
8 7即：
a[l-1] a[r+1]这正是区间DP的精髓。
第七幕：为什么要按区间长度枚举？
1、先算：
长度1即：
f[1][1] f[2][2] ...2、再算：
长度23、再算：
长度3...........
4、因为：
f[l][r]要依赖：
f[l][k-1] f[k+1][r]这些区间都更短。
必须先算。
第八幕：画图理解
1、假设：
1 6 32、长度1：
f[1][1] f[2][2] f[3][3]3、长度2：
f[1][2] f[2][3]4、长度3：
f[1][3]这样：
每次用到的状态都已经有了。
第九幕：参考代码解析
#include <iostream> #include <algorithm> using namespace std; // n：数字个数 int n; // a[i]：第 i 个数字 // 注意：a[0] 和 a[n+1] 默认都是0 // 表示最左边、最右边没有邻居时，贡献为0 int a[110]; // f[l][r] // 表示把区间 [l,r] 内的所有数字全部删除 // 能够获得的最大得分 long long f[110][110]; int main() { cin >> n; // 输入数字 for (int i = 1; i <= n; i++) cin >> a[i]; // ========================== // 区间DP开始 // ========================== // len：当前枚举的区间长度 for (int len = 1; len <= n; len++) { // 枚举所有长度为len的区间 // // 例如 len=3 // // [1,3] // [2,4] // [3,5] // ...... // for (int l = 1, r = len; r <= n; l++, r++) { // 假设 k 是区间中最后一个被删除的数字 // // k 可以是： // // l // l+1 // ... // r // // 全部尝试一遍 // for (int k = l; k <= r; k++) { // 左半部分已经全部删除 long long leftScore = f[l][k - 1]; // 右半部分已经全部删除 long long rightScore = f[k + 1][r]; // 最后删除k时 // // 区间[l,r]里面已经没有其它数字 // // 所以它左右两侧一定是： // // a[l-1] // a[r+1] // long long lastScore = a[l - 1] + a[r + 1]; // 更新答案 f[l][r] = max( f[l][r], leftScore + rightScore + lastScore ); } } } // 删除整个数组得到的最大得分 cout << f[1][n] << endl; return 0; }1、含义：
第一层
i区间长度。
第二层
l,r枚举区间。
第三层
k枚举最后删除的人。
2、标准区间DP模板：
区间长度 ↓ 区间位置 ↓ 断点/最后操作点第十幕：本题和戳气球的关系
其实本题和经典题：
《Burst Balloons》
几乎一模一样。
1、戳气球：
最后戳哪个？2、本题：
最后删哪个？3、核心思想完全一致：
不要想第一个操作谁，而要想最后一个操作谁。
这是区间DP最重要的思维方式。
4、时间复杂度
（1）三层循环：
长度 O(n) 区间 O(n) 最后删除点 O(n)所以：
O(n³)（2）题目：
n ≤ 100因此：
100³=1000000一百万次左右。
完全能通过。
本题总结：
这道题的本质是：
区间DP + 最后删除法。
1、定义
f[l][r]表示删除区间[l,r]的最大收益。
2、枚举区间中最后被删除的位置k：
f[l][r] = max( f[l][k-1] + f[k+1][r] + a[l-1] + a[r+1] );3、然后按照区间长度从小到大进行DP即可。
4、必须记住的区间DP口诀
不会删第一个？ 就想删最后一个！ 不会合并第一个？ 就想合并最后一个！ 区间DP三板斧： ① 状态是什么？ ② 最后操作谁？ ③ 按长度转移。
