GESP 2025年3月 真题 环线 完整题解（动态规划）

记录一道 GESP 2025年3月 的动态规划真题。这类题在考试里属于必得分项，核心就那几行代码，关键是别在小细节上丢分。

题目来源：ACGO A75439 ｜ 2025年3月 六级
赛事场次：2025年3月 六级

一、题目信息

题目名称：环线

赛事场次：2025年3月 六级

难度定位：六级

涉及知识点：单调队列 动态规划

题目链接：https://www.acgo.cn/problemset/info/75439

先说坑点（不提前知道必错）

• 状态定义、状态转移方程、初始化、遍历顺序四要素。

题意简述

小 A 喜欢坐地铁。地铁环线有 n 个车站，依次以 1,2,⋯,n 标号。车站 i(1≤i<n) 的下一个车站是车站 i+1 ，特殊地，车站 n 的下一个车站是车站 1。小 A 会从某个车站出发，乘坐地铁环线到某个车站结束行程，这意味着小 A 至少会经过一个车站。小 A 不会经过一个车站多次。当小 A 乘坐地铁环线经过车站 i 时，小 A 会获得 aᵢ 点快乐值。请你安排小 A 的行程，选择出发车站与结束车站，使得获得的快乐值总和最大。

前置知识

下面先把需要的基础知识理一遍，不熟悉的朋友可以跟着看，熟悉的直接跳过。

读懂题意：先把题目要求的输入输出格式看清楚，明确我们要算什么、按什么格式输出，这是所有题的第一步。

二、思路分析

先看清楚题目要我们做什么

把题目读两遍，我们提取出关键信息：输入是什么、要输出什么、有哪些约束条件。这道题考查的是动态规划，属于这类题里比较基础的一道，把题目要求一步步翻译成代码逻辑就能解决。

我的思考过程

读完题之后，我的第一反应是这样的：环形 n 个车站，从某站出发到某站结束，途经连续一段（不重复经过车站），获得途经站点的快乐值之和，求最大值。环形最大子段和：不能取整圈。答案 = max(不环绕的最大子段和, 总和 - 最小子段和)。用 Kadane 求最大子段和与最小子段和，再考虑环绕情况（总和减最小子段和）。注意全为负数时（不取整圈）答案取单个最大值。

需要说明的是，上面这个思路是把题目要求直译成代码得到的，没有用到什么高级技巧。对于这类基础题，读准题意加写对边界比追求巧妙解法更重要，因为考试里这种题是必须拿满分的。

三、完整代码 + 逐行注释

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

int n;
long long a[500010], pre[500010];
int q[500010], ql, qr;
long long ans;
int main() {
    cin>>n;  // 读入
    for (int i = 1; i <= n; i++) {  // 遍历
        cin>>a[i];  // 读入
        a[n + i] = a[i];
    }
    for (int i = 1; i <= 2 * n; i++)  // 遍历
        pre[i] = pre[i - 1] + a[i];
    ql = qr = 1;
    ans = -1e18;
    for (int i = 1; i <= 2 * n; i++) {  // 遍历
        while (ql <= qr && q[ql] < i - n)
            ql++;
        ans = max(ans, pre[i] - pre[q[ql]]);
        while (ql <= qr && pre[i] < pre[q[qr]])
            qr--;
        q[++qr] = i;
    }
    cout<<ans<<endl;  // 输出
    return 0;
}

四、代码分段拆解

代码不长，但每一段都有讲究，我们分段拆开看。

第一步：引入头文件

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

#include <iostream> 提供输入输出功能，using namespace std; 让我们能直接写 cin、cout 而不用加前缀。这两行是几乎所有 C++ 程序的开头，照写即可。

第二步：读入数据

    cin>>n;
        cin>>a[i];

注意变量的类型要能装下题目的数据。数据可能超过 21 亿时要改用 long long。

第三步：核心处理逻辑

    for (int i = 1; i <= n; i++) {
    for (int i = 1; i <= 2 * n; i++)
    for (int i = 1; i <= 2 * n; i++) {
        while (ql <= qr && q[ql] < i - n)

这一段是整道题的关键，也是动态规划的体现。看循环的三个要素：从哪里开始、什么时候结束、每次怎么变化。这三个要素任何一个写错，结果都会不对。

第四步：按要求输出

    cout<<ans<<endl;

输出格式必须和题目要求的完全一致。很多同学算法完全正确却因为少了一个换行或者空格多寡不对而 WA，这种分丢得最可惜。

五、实例模拟

把样例代进去手动模拟一遍，思路会更清晰。

以题目的第一组样例为例：

样例输入

4
-1 2 3 0

样例输出

5

把这份输入代进代码，程序会先把数据依次读入，然后进入循环逐个判断，把满足条件的值累积起来，最后按格式输出。建议你对照着代码在纸上走一遍前两次循环，确认自己对每一步的理解都和程序一致。

题目另外还给了 1 组样例，做完之后建议把剩下的样例都跑一遍，全部通过再提交，能避开大部分边界问题。

六、踩坑总结

下面是做这道题时最容易出错的地方，对照自己的代码检查一下：

1. 变量类型选错：虽然本题范围不大，但养成习惯——凡是不确定范围时，累加变量一律用 long long，成本为零但能保命。
2. 区间边界取错：题目说「L 到 R 之间包括两端」，循环就要写 for (int i = L; i <= R; i++)。写成 i < R 会漏掉最后一个数，这是最常见的失分点。
3. 输出格式不符：题目要求输出几行就输出几行，行末换行、数字之间的空格都要严格对齐，算法对了但格式错了同样判 WA，这种分丢得最冤。
4. 特殊情况没特判：把最小数据、最大数据、答案恰好等于 0 的情况各测一遍。特别是边界输入，出题人最喜欢在这里设陷阱。

七、知识点拓展

这题虽然简单，但背后的方法可以推广，总结如下：

• 本题考查动态规划的基本写法，这类题在考试中属于必得分项，要练到能默写。
• 写完代码后建议自己造几组边界数据测试，特别是最小值和最大值。
• 同一知识点在不同场次反复出现，把这道题的写法吃透，后面遇到同类题可以直接套用。

八、适用人群

刚学完动态规划、正在准备 六级 考试的同学，适合用这道题检验掌握程度。

以上就是这道题的全部内容。这个系列会按考试场次逐题更新，觉得有帮助的话可以关注一下，也欢迎在评论区留下你的解法。

转载自 CSDN-专业IT技术社区

原文链接：https://blog.csdn.net/stillwatersss/article/details/169914251