ARTICLE · 1370823
GESP 2025年3月 真题 环线 完整题解(动态规划)
小 A 喜欢坐地铁。地铁环线有 n 个车站,依次以 1,2,⋯,n 标号。车站 i(1≤i<n) 的下一个车站是车站 i+1 ,特殊地,车站 n 的下一个车站是车站 1。小 A 会从某个车站出发,乘坐地铁环线到某个车站结束行程,这意味着小 A 至少会经过一个车站。小 A 不会经过一个车站多次。当小 A 乘坐地铁环线经过车站 i 时,小 A 会获得 aᵢ 点快乐值。请你安排小 A 的行程,选择出发车站与结束车站,使得获得的快乐值总和最大。
-1 2 3 0
-3 4 -5 1 3
这题有两种写法:一种三分钟能写对但过不了大数据,一种要想一会儿但能拿满分。两种都讲。
这道题出自 GESP 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 的行程,选择出发车站与结束车站,使得获得的快乐值总和最大。
一句话概括:用单调队列 动态规划把题目要求原样翻译成代码,属于考场上必须拿满分的题。
| 初版(只想让样例过) | 定稿(能拿满分) | |
|---|---|---|
| 数据类型 | int 一把梭 | long long 声明累加变量 |
| 边界 | 只试样例那组 | 题目说「到」或者「包括」 |
| 输出 | cout << ans; | 按题目要求补换行与空格 |
初版和定稿的算法是同一个,差的只是这三处。
先看初版怎么想:把题面逐句翻译,能跑样例就算完。这条路能拿到分,但只在小数据上。
环形 n 个车站,从某站出发到某站结束,途经连续一段(不重复经过车站),获得途经站点的快乐值之和,求最大值。环形最大子段和:不能取整圈。答案 = max(不环绕的最大子段和, 总和 - 最小子段和)。用 Kadane 求最大子段和与最小子段和,再考虑环绕情况(总和减最小子段和)。注意全为负数时(不取整圈)答案取单个最大值。
两条路的分岔点只有一个:动笔前有没有先算一遍账。
建议先自己写二十分钟,卡住了再看。对着抄一遍的效果,比不上自己错一遍。
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;
}
整份代码里真正需要想清楚的只有两处,我们只看这两处。
第一段,把数据读进来。
读入这段只要盯一件事:变量类型装不装得下。其他都可以照抄。
第二段,核心处理。
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]])
// …(这段后面还有,见上面的完整代码)
这段是整道题唯一需要想的地方,也是动态规划的落点。看循环时只问三句:从哪开始、到哪结束、每次加几。三句都对,这段就没错。
下面按四步验一遍,这个顺序建议你考试时也照做。
样例输入
-1 2 3 0
样例输出
| 步骤 | 做什么 | 通过标准 |
|---|---|---|
| 1 | 把第一组样例抄进去跑 | 一个字都不差,行尾空格也别多 |
| 2 | 换成最小规模 | n = 1 或只有一组数据时不崩,结果符合题意 |
| 3 | 检查输出末尾 | 没有多余空格,最后一行有换行 |
| 4 | 跑完剩下 1 组样例 | 全部对上再提交,别只看第一组 |
题目还有 1 组样例,全部跑通再提交。
| 容易错的地方 | 错误写法 | 正确写法 |
|---|---|---|
| 累加结果溢出 | int sum = 0; | long long 声明累加变量 |
| 漏掉区间右端点 | i < R | i <= R |
| 输出格式不符 | cout << ans; | cout << ans << "\n"; |
| 多组数据没清空 | 全局数组直接用 | 每组数据前 memset 或重新赋值 |
这题的经验压缩成三行,考前扫一眼就够。
- 两个版本的差别:算法相同,差在类型、边界、输出三处。
- 要记住的:先把
dp[i]的含义写成一句人话,比如「前 i 个物品的最优值」,定义错了后面全白写。 - 下一步:下一题动笔前先花两分钟算范围和边界。
系列按场次往前推,下一篇还在这个级别,难度会往上走一档。
- 本文属于《GESP 真题题解》系列,第 74 篇,真题按年份持续补齐,每篇都带完整可编译代码,题号可在 ACGO 直接提交验证。
- 还没动笔的话,先自己写一遍再回来看踩坑总结,比直接照抄代码收获大。
- 想跟完整系列的朋友点个关注,更新会第一时间推送。
- 本系列合集目录(按年份/组别排序)
GESP 的坑多半在边界和读题上。这道动态规划题把该注意的点都列在上面的表里了,提交前逐条过一遍。
今天想问你:这道题你第一次交是 WA 还是 AC?卡在哪一步,评论区说说,我帮你看看。
有用就收藏一份,考前翻出来快速过一遍错题点;关注本号,真题系列每天不间断。
想要这题的可运行代码文件?后台回复 “资料” 直接拿。
本篇编号 GESP-047(公众号 MP-047)。完整目录与更多题解见博客专栏(公众号菜单「历史文章」)。















































































