夜雨聆风学习资料网

ARTICLE · 1370823

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

GESP 2025年3月 真题 环线 完整题解(动态规划)
【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
输入
4
-1 2 3 0
输出
5
样例 2
输入
5
-3 4 -5 1 3
输出
5
题解正文

这题有两种写法:一种三分钟能写对但过不了大数据,一种要想一会儿但能拿满分。两种都讲。

这道题出自 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 求最大子段和与最小子段和,再考虑环绕情况(总和减最小子段和)。注意全为负数时(不取整圈)答案取单个最大值。

读入数据 → 预处理前缀和 → 按格式输出

两条路的分岔点只有一个:动笔前有没有先算一遍账。

四、能拿满分的写法

建议先自己写二十分钟,卡住了再看。对着抄一遍的效果,比不上自己错一遍。

#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;
}
五、和暴力版的差别只在两处

整份代码里真正需要想清楚的只有两处,我们只看这两处。

第一段,把数据读进来。

    cin>>n;

读入这段只要盯一件事:变量类型装不装得下。其他都可以照抄。

第二段,核心处理。

    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]])
    // …(这段后面还有,见上面的完整代码)

这段是整道题唯一需要想的地方,也是动态规划的落点。看循环时只问三句:从哪开始、到哪结束、每次加几。三句都对,这段就没错。

六、先对答案,再看耗时

下面按四步验一遍,这个顺序建议你考试时也照做。

样例输入

4
-1 2 3 0

样例输出

5
步骤做什么通过标准
1把第一组样例抄进去跑一个字都不差,行尾空格也别多
2换成最小规模n = 1 或只有一组数据时不崩,结果符合题意
3检查输出末尾没有多余空格,最后一行有换行
4跑完剩下 1 组样例全部对上再提交,别只看第一组

题目还有 1 组样例,全部跑通再提交。

七、两种写法各自的坑
容易错的地方错误写法正确写法
累加结果溢出int sum = 0;long long 声明累加变量
漏掉区间右端点i < Ri <= R
输出格式不符cout << ans;cout << ans << "\n";
多组数据没清空全局数组直接用每组数据前 memset 或重新赋值
八、复杂度账本

这题的经验压缩成三行,考前扫一眼就够。

  • 两个版本的差别:算法相同,差在类型、边界、输出三处。
  • 要记住的:先把 dp[i] 的含义写成一句人话,比如「前 i 个物品的最优值」,定义错了后面全白写。
  • 下一步:下一题动笔前先花两分钟算范围和边界。

系列按场次往前推,下一篇还在这个级别,难度会往上走一档。


系列导航
  • 本文属于《GESP 真题题解》系列,第 74 篇,真题按年份持续补齐,每篇都带完整可编译代码,题号可在 ACGO 直接提交验证。
  • 还没动笔的话,先自己写一遍再回来看踩坑总结,比直接照抄代码收获大。
  • 想跟完整系列的朋友点个关注,更新会第一时间推送。
  • 本系列合集目录(按年份/组别排序)
写在最后

GESP 的坑多半在边界和读题上。这道动态规划题把该注意的点都列在上面的表里了,提交前逐条过一遍。

今天想问你:这道题你第一次交是 WA 还是 AC?卡在哪一步,评论区说说,我帮你看看。

有用就收藏一份,考前翻出来快速过一遍错题点;关注本号,真题系列每天不间断。

想要这题的可运行代码文件?后台回复 “资料” 直接拿。

本篇编号 GESP-047(公众号 MP-047)。完整目录与更多题解见博客专栏(公众号菜单「历史文章」)。

回首页,搜索你想要的文档

在首页搜索框输入关键词,快速定位资料

文库首页搜索指引 立即搜索

相关学习资料