🤳🏻202606 GESP 7 级第 2 题

2026 年 06 月的这次 GESP 几乎是大放水。几乎所有级别的整体难度跟前两次相比是降低的。

但是 7 级却出现了一点意外。也就是 7 级的第二题。网上爆出很多同学都不会做。当时我再带另一个比赛没有去细查什么情况。

直到官方发布真题后，我第一时间下载了 7 级试卷去看了看。然后我的第一反应是 “这难道不是很模板的水题吗？”

然后仔细一想发现不对，哦，原来又是“超纲”。

让我们来看下现在 7 级的考纲。

知识内容	知识目标
数学库常用函数（三角、对数、指数） 复杂动态规划（二维动态规划、动态规划最值优化） 图的定义及遍历 图论基本算法（图的深度优先遍历、广度优先遍历、泛 洪算法） 哈希表	掌握图的定义与遍历相关算法，掌握图论基本概念及基础算法，能使用二维动态规划、动态规划最值优化的知识完成复杂的动态规划算法

为什么我上面的超纲打引号，因为考纲里的动态规划说得非常模糊。复杂动态规划能有多复杂？二维动态规划是可以降到1维那种？还是从3维降下来的？

所以说从网上的现象看来，目前大多数机构或者课程是很少有讲过本次的这种题型，也就是区间DP。

其实区间DP是在各种专业竞赛的书籍和题单里必定会出现的一个常见知识点，但是我不知道为什么这类机构不讲这个。也许是。。。？

🤳🏻题面

P17015 GESP202606 七级 消消乐 - 洛谷

P17015 [GESP202606 七级] 消消乐

题目描述

给定一个由 $n$ 个整数构成的数组 $a=[a_1,\dots ,a_n]$。每次你可以对数组 $a$ 进行以下操作，直到数组 $a$ 变为空：

• 指定 $a$ 中的一个元素，获得该元素两侧相邻元素之和的分数，并将该元素从 $a$ 中删去。

特别地，如果相邻元素不存在则该元素的值视为 $0$。例如，对于 $a=[1,2,3]$ 可以进行以下操作：

• 指定元素 $2$，获得分数 $1+3$，删去 $2$ 后 $a=[1,3]$；
• 指定元素 $1$，获得分数 $0+3$，删去 $1$ 后 $a=[3]$；
• 指定元素 $3$，获得分数 $0+0$，删去 $3$ 后 $a$ 变为空。

请问你能获得的分数总和最大是多少？

输入格式

第一行，一个正整数 $n$，表示数组长度。

第二行，$n$ 个非负整数 $a_1,\dots ,a_n$，表示数组 $a$ 中的整数。

输出格式

输出一行，一个整数，表示能获得的最大分数总和。

输入输出样例 #1

输入 #1

6
1 6 3 2 9 1

输出 #1

55

输入输出样例 #2

输入 #2

5
3 1415 926 53 58

输出 #2

5771

说明/提示

数据范围

对于 $40\%$ 的测试点，保证 $1\le n\le 50$，$0\le a_i\le 10^3$。

对于所有测试点，保证 $1\le n\le 100$，$0\le a_i\le 10^9$。

🤳🏻解

#include <bits/stdc++.h>
using namespace std;

const int M = 10 + 1e2;

int arr[M];
int dp[M][M];

int main() {
    int n;
    cin >> n;
    for (int i = 1; i <= n; i += 1) {
        cin >> arr[i];
    }

    // 区间 dp
    // 枚举区间长度
    for (int len = 1; len <= n; len += 1) {
        // 枚举区间的左右端点
        for (int i = 1, j = i + len - 1; j <= n; i += 1, j += 1) {
            // 划分区域 [i, k-1] [k] [k+1, j]
            for (int k = i; k <= j; k += 1) {
                dp[i][j] = max(dp[i][j]  // 松弛
                               ,
                               (dp[i][k - 1] + dp[k + 1][j])  // 两边的 dp
                            +  (arr[i - 1] + 0 + arr[j + 1])  // 区间外的两个测（题意得贡献）
                );
            }
        }
    }

    cout << dp[1][n] << endl;
    return 0;
}

类似题：

leetcode - 312. 戳气球

hdu - 5115 Dire Wolf

🤳🏻END

题外话

hdu - 5115 Dire Wolf 是 2014 ACM/ICPC 亚洲区北京站的一道真题。在 hdu 上是有收录的。

我想看看在洛谷上有没有收录，然后我在洛谷上搜了搜，没有。

然后我去让 DeepSeek 帮我查查，然后 DeepSeek 告诉我没有。但让我看到了另一个东西。

然后我尝试点开看一下，发现 404 了。

其实这篇是我在 2022 年的时候写在 CSDN 上的一篇 区间DP 的博客，只是估计又被哪个网站收编了。然后这个网站的这个节点 404 了。然后导致我这个作者都看不了了😅。

原文如下：(区间dp) (经典例题) 石子合并 -CSDN博客