这道GESP 七级 2026 年 6 月编程题第二题《消消乐》如果按照考试难度来评价我认为⭐⭐⭐⭐⭐这是本套试卷中最难的一题。很多同学看到题目后会想到贪心模拟链表删除区间DP事实上这是一道非常经典的区间DP题。而且它和很多NOIP、CSP中的经典题戳气球石子合并矩阵连乘都有相同的思想。第一幕神秘的消消乐游戏1、假设有一排数字1 6 3 2 9 11题目说每次选一个数字删掉。获得左邻居 右邻居的分数。2如果不存在邻居算02、例如1 6 31删除6获得1342然后变成1 3继续删。3最后删光。4问怎样删除才能获得最大总分第二幕为什么贪心不行1、有的同学第一反应每次删当前收益最大的。例如1 6 3 2 9 1先删2获得3912看起来不错。但这样做以后后面的结构全部改变了。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]最后删的是k2那么[l......k-1]先删完。获得f[l][k-1]3然后[k1......r]也删完。获得f[k1][r]4最后轮到k被删。此时区间内部已经空了。只剩边界了。5于是k获得的分数就是a[l-1] a[r1]2、所以转移公式f[l][r] max( f[l][r], f[l][k-1] f[k1][r] a[l-1] a[r1] );这是本题的核心。第六幕为什么是 a[l-1] 和 a[r1]1、这是本题中需要重点理解的地方。很多同学会问为什么不是 a[k-1] 和 a[k1]2、因为我们讨论的是最后删除k的时候。3、此时[l,r]内部已经全部删光。4、例如8 1 6 3 2 71考虑区间[2,5]即1 6 3 2全部删除。2如果最后删的是33那么1 6 2都已经没了。4此时3两边是谁不是6 2因为它们已经消失。5而是区间外面的8 7即a[l-1] a[r1]这正是区间DP的精髓。第七幕为什么要按区间长度枚举1、先算长度1即f[1][1] f[2][2] ...2、再算长度23、再算长度3...........4、因为f[l][r]要依赖f[l][k-1] f[k1][r]这些区间都更短。必须先算。第八幕画图理解1、假设1 6 32、长度1f[1][1] f[2][2] f[3][3]3、长度2f[1][2] f[2][3]4、长度3f[1][3]这样每次用到的状态都已经有了。第九幕参考代码解析#include iostream #include algorithm using namespace std; // n数字个数 int n; // a[i]第 i 个数字 // 注意a[0] 和 a[n1] 默认都是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的区间 // // 例如 len3 // // [1,3] // [2,4] // [3,5] // ...... // for (int l 1, r len; r n; l, r) { // 假设 k 是区间中最后一个被删除的数字 // // k 可以是 // // l // l1 // ... // 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[r1] // 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、枚举区间中最后被删除的位置kf[l][r] max( f[l][k-1] f[k1][r] a[l-1] a[r1] );3、然后按照区间长度从小到大进行DP即可。4、必须记住的区间DP口诀不会删第一个 就想删最后一个 不会合并第一个 就想合并最后一个 区间DP三板斧 ① 状态是什么 ② 最后操作谁 ③ 按长度转移。