★ FEATURED ARTICLE 1. 题目到底在说什么先把题意嚼碎了再动手先别急着看代码。做这道题最容易翻车的地方根本不是算法本身而是题意理解不到位。P1070这道“道路游戏”题面绕来绕去核心其实可以压缩成一句话在一个环形道路上每个时间点每个位置都有一个“买机器人”的价格机器人会沿固定方向走边走边收金币每个时间点至多只能买一个机器人新买的机器人起点自选、花费自选问一段时间内能净赚多少。我第一次做的时候把“每个时间点至多买一个”理解成了“每个位置至多买一个”结果样例都过不去卡了整整一个晚上。后来才反应过来题面说的是每个单位时间结束后你可以选择买一个新机器人也可以不买买了之后它会从你指定的位置出发在当前时间点立刻开始走并且持续走P步。这里有几个关键细节必须掰开揉碎道路是环形的。位置从1到n机器人往编号增大的方向走走到n之后回到1。这个“环形”是第一个坑很多人的前缀和写到最后越界就是因为忘了取模。每个时间点道路上每个位置都会生成若干金币但这些金币只存在一个单位时间。也就是说第i秒第j个位置的金币只有第i秒经过这里的机器人能捡到错过就没了。机器人最多能走P步P是全局给定的一个常数。走完P步之后无论走到哪里机器人就报废了必须重新买。买机器人的花费是你买它的那个时间点、那个位置上的单价。也就是说第t时刻在位置i买机器人花费是buy[t][i]跟机器人之后走多远、捡多少钱没有关系。理清这四点之后题意的建模就顺了。本质上这题是让你在时间维、位置维、步数维三者之间做取舍每一步都面临“续还是不续”的选择——续就继续用当前机器人省下一笔购买费不续就花掉一笔新购买费换来一个可能更优的起点。这个“续命”和“换新”的博弈全题的核心就在这里。2. 暴力思路打底先写出能过的朴素解法再谈优化很多题解上来就推DP公式我建议你先自己写一版暴力哪怕只有30分也能帮你建立对题意的直觉。暴力思路其实非常直白枚举每一个时间点枚举机器人起点枚举机器人走的步数把所有情况都算一遍取最大值。假设当前时间是t起点是s机器人走了k步1 ≤ k ≤ P那么它捡到的金币总数就是从(t, s)开始沿着时间递增、位置递增的方向连续k个格子上的金币之和。这一步用前缀和优化一下复杂度立刻降一个量级。不过纯暴力的话状态数是T * n * P对每个状态再枚举起点就是T * n * P * n在T1000, n1000, P1000的数据范围下直接爆掉。但别忘了暴力解法还有一个额外收益它能帮你验证“每个时间点至多买一个机器人”这个限制。我刚开始写暴力时就试过“每个时间点买多个机器人”的版本发现金币总量直接翻倍样例全错这才逼着自己回去重新读题。所以我的建议是先写暴力不是为了拿分是为了逼自己看懂题。下面是一版30分左右的暴力参考逻辑上非常朴素但结构清晰方便后面和正解对照#include bits/stdc.h using namespace std; const int N 1005; int n, m, p; int gold[N][N]; // gold[t][i] 表示第t时刻位置i的金币 int cost[N][N]; // cost[t][i] 表示第t时刻位置i的买机器人单价 int dp[N]; // dp[t] 表示前t时刻的最大净收益 int main() { scanf(%d%d%d, n, m, p); for (int i 1; i n; i) for (int t 1; t m; t) scanf(%d, gold[t][i]); for (int i 1; i n; i) for (int t 1; t m; t) scanf(%d, cost[t][i]); memset(dp, -0x3f, sizeof(dp)); dp[0] 0; for (int t 1; t m; t) { for (int s 0; s n; s) { // 枚举机器人起点0-based方便取模 int sum 0; for (int k 1; k p t k - 1 m; k) { int pos (s k - 1) % n; sum gold[t k - 1][pos]; // 从dp[t-1]转移过来即前t-1时刻的最优值 // 加上当前机器人捡的金币减去买机器人的花费 int profit sum - cost[t][s]; dp[t k - 1] max(dp[t k - 1], dp[t - 1] profit); } } } printf(%d\n, dp[m]); return 0; }这版代码的转移公式是核心dp[tk-1] max(dp[tk-1], dp[t-1] sum - cost[t][s])。意思是我在第t时刻买了一个起点为s的机器人它连续走k步捡了sum金币花掉cost[t][s]那么到tk-1时刻为止的收益就是前t-1时刻的收益加上这一段的净赚。这个公式里藏着两个关键为什么是dp[t-1]而不是dp[t]因为每个时间点只能买一个机器人所以买机器人的动作发生在t时刻开始之前而t时刻之前的状态已经由dp[t-1]锁定了。如果你写成dp[t]就会在下一次转移时重复计算同一时刻的购买导致逻辑混乱。为什么是sum - cost[t][s]而不是单独算每一步因为一次购买对应一段连续的行走买机器人的花费一次出金币分批进合在一起算净收益才是对的。暴力版能过样例但提交上去基本只有30分左右因为O(m * n * p)的复杂度在数据一大就炸。不过没关系它的存在意义在于帮你确认转移方向和高层公式接下来所有优化都是在这条转移线上做文章。3. 正解推导从暴力公式一路推到O(mn)的单调队列优化3.1 先把转移公式做一个“代数变形”让优化方向浮出来暴力版的dp[tk-1] max(dp[t-1] sum - cost[t][s])细看其实可以拆成两部分一部分是和起点s、步数k强相关的“可变收益”另一部分是和时间点t强相关的“固定花费”。如果我们把tk-1看作一个整体设j tk-1那么对于不同的t和k可能对应同一个j这就是优化的突破口。转换一下视角我们其实是在枚举“机器人走的最后一步”对应的时刻j然后反推“机器人在哪一刻被买的”。假设机器人在t时刻被买走了k步最后一步落在j时刻那么t j - k 1。换句话说对于每个j我们想知道在j时刻结束之前我最后一次买机器人应该选在什么时刻、什么起点才能让总收益最大这个“最后一次购买”的视角是单调队列优化的关键。因为机器人最多走p步所以t的取值范围是[j-p1, j]。那么对每个j我们要枚举所有可能的t和起点s计算对应的收益取最大值。这个枚举的规模还是很大但如果我们能把s这一维也消掉就会变成一个一维的滑动窗口问题。我先把公式改写一下。设pre是金币的二维前缀和预处理数组但这里有一个细节——因为道路是环形的金币的产生是随时间走的所以前缀和并不是简单的二维前缀而是需要沿着“时间-位置”斜线方向做前缀和。具体来说设sum[t][i]表示“从第1时刻位置1开始沿着机器人行走方向连续累计到时刻t位置i的金币总和”那么一个机器人从起点s走k步捡到的金币就等于sum[tk-1][(sk-1)%n] - sum[t-1][(s-1n)%n]。这个斜向前缀和我建议你自己画个表格验证一遍不然很容易写错。有了这个前缀和dp[j]的转移可以写成dp[j] max(dp[t-1] - cost[t][s] sum[j][(sk-1)%n] - sum[t-1][(s-1n)%n])其中k j - t 1所以(sk-1)%n (s j - t)%n。这个式子看起来很复杂但注意sum[j][...]这一项对给定的j和s来说只取决于一个变量而dp[t-1] - cost[t][s] - sum[t-1][(s-1n)%n]这一部分只取决于t和s和j无关。这意味着**对于每个固定的t和s它的“贡献值”是可以预先算出来的然后在j从t到tp-1的范围内这个贡献值都要参与比较。**这就是标准的滑动窗口最大值问题——每个时刻t产生一个值这个值在接下来p个时刻内都有效我们需要维护一个窗口内的最大值。3.2 位置维度的处理按取模结果分组在动手写单调队列之前还有一个大坑必须先解决环形道路的位置编号经过取模之后规律不是线性的而是分布在不同的“同余类”里。细看转移式(sj-t)%n这个下标对固定的t和sj每增加1位置下标也增加1取模。所以如果一个单调队列直接按时间维滑动队列里的元素会对应不同位置的值无法直接比较。解决办法是按(j - s)在同余意义下的值进行分组也就是把位置维和时间维的差值一起考虑。具体做法是枚举一个基准位置s然后只看那些满足(j - s) % n为定值的(t, j)组合。换句话说同一组内的元素它们的“相对位移”是一样的这样滑动窗口里的比较才有意义。我当初卡在这里很久后来是看了一个题解里“按对角线分组”的表述才豁然开朗——你不需要同时枚举所有的起点s而是按(s - t) mod n的值分成n组每一组独立维护一个单调队列。为什么按(s - t) mod n分组因为观察转移式里的(sj-t)%n如果j变成j1同时我们只关心那些(s-t)保持不变的情况那么(sj-t)也跟着加1。在这个分组内(sj-t)%n的变化是纯粹线性的单调队列的维护逻辑就通了。实际上更常见的写法是对于每个余数r (s - t) mod n把对应的时间点t依次处理维护一个单调递减队列。队列里存的是“候选的t值”队首是当前窗口内贡献值最大的那个t。窗口长度是p所以队首元素如果太老t j-p1就弹出。3.3 完整的状态转移实现从0到1把代码写出来说了这么多理论直接上代码。下面的实现是O(mn)的配合单调队列优化能在标准数据范围内稳定通过#include bits/stdc.h using namespace std; const int N 1005; const int INF 0x3f3f3f3f; int n, m, p; int gold[N][N]; // gold[t][i] 第t时刻位置i的金币位置用0-based int cost[N][N]; // cost[t][i] 第t时刻位置i的买机器人花费 int dp[N]; int sum[N][N]; // 斜向前缀和sum[t][i] 表示从(1,0)沿行走方向到(t,i)的金币累计 int main() { scanf(%d%d%d, n, m, p); for (int i 0; i n; i) for (int t 1; t m; t) scanf(%d, gold[t][i]); for (int i 0; i n; i) for (int t 1; t m; t) scanf(%d, cost[t][i]); // 预处理斜向前缀和 // sum[t][i] gold[t][i] sum[t-1][(i-1n)%n] (t1) // 基准sum[0][i] 0 memset(sum, 0, sizeof(sum)); for (int t 1; t m; t) { for (int i 0; i n; i) { sum[t][i] gold[t][i] sum[t-1][(i-1n)%n]; } } memset(dp, -0x3f, sizeof(dp)); dp[0] 0; // 对每个取模余数分组每组维护单调队列 for (int r 0; r n; r) { // 队列里存的是时间t对应的贡献值 // 贡献值 dp[t-1] - cost[t][s] - sum[t-1][(s-1n)%n] // 其中 s (r t) % n因为 r (s - t) % n dequeint q; // 初始化把 t0 当作一个“预备购买点” // 但我们只关心 t1 的购买动作先把t1放进去 for (int t 0; t m; t) { // 计算当前位置 s int s (r t) % n; // 如果当前t可以作为购买时间即t1计算候选值并入队 if (t 1) { int val dp[t-1] - cost[t][s] - sum[t-1][(s-1n)%n]; // 维护队列的单调性队尾的值如果比当前val小就弹出 while (!q.empty()) { int old_t q.back(); int old_s (r old_t) % n; int old_val dp[old_t-1] - cost[old_t][old_s] - sum[old_t-1][(old_s-1n)%n]; if (old_val val) q.pop_back(); else break; } q.push_back(t); } // 弹出窗口外的元素窗口是[j-p1, j] // 此时j t注意t递增对应当前时间点j // 如果队首的购买时间太老即 old_t t - p 1就弹出 while (!q.empty() q.front() t - p 1) q.pop_front(); // 此时队首就是最优候选 if (!q.empty() t 1) { int best_t q.front(); int best_s (r best_t) % n; int val dp[best_t-1] - cost[best_t][best_s] - sum[best_t-1][(best_s-1n)%n]; dp[t] max(dp[t], val sum[t][(r t) % n]); } } } printf(%d\n, dp[m]); return 0; }这段代码我逐行解释一下因为里面满是细节稍不留神就错sum[t][i]的预处理是斜向前缀和。注意递推式里的(i-1n)%n这才是环形道路的正确写法。如果你用普通二维前缀和样例可能碰巧对但大数据一定错。分组循环里r表示(s-t)%n的余数。对于一个给定的r当t遍历0到m时s(rt)%n自然就是在同一个“对角线”上移动。这保证我们在同一组内维护单调队列时跨过环形边界位置的变化是连续的。队列里的元素是“候选购买时刻t”。每次新到一个时刻t先计算以当前t为购买时刻的候选值val插入队列然后弹出过期的tt j-p1最后队首就是当前jt的最优购买时刻。我特意在处理时保留了t0这个边界但t0不能作为购买时刻所以插入队列时加了if (t 1)的限制。这个细节很多人会漏一漏就是边界WA。这个写法是最容易理解的单调队列版本。实际提交时你还可以把单调队列用数组模拟减少deque的开销不过deque在数据范围不大时已经够快优先保证正确性。3.4 为什么单调队列能用在这里本质是“有效期滑动”很多新手学单调队列只知道模板不知道什么时候用。这道题是一个非常典型的场景有一个值在某个时间区间内有效并且我们要动态维护区间内的最大值。具体来说每个购买时刻t对应一个贡献值val(t)这个贡献值从t时刻开始生效持续到tp-1时刻。当时间推进到j时所有满足t ∈ [j-p1, j]的val(t)都有效我们要取其中最大值。这就是一个标准的“滑动窗口最大值”问题窗口左端和右端都单调递增所以可以用单调队列。关键在于val(t)的计算中包含了dp[t-1]而dp[t-1]是已经确定的历史最优值不会因为j的改变而改变。这就保证了单调队列的“静态值”特性——队列中的每个值在插入时就可以确定之后不会变化只有“过期”和“淘汰”的问题。如果val(t)还依赖j那就没法用简单的单调队列了得用其他手段。再深一层为什么每组单独维护队列因为val(t)的计算里隐含了一个s (rt)%n的关联不同组的s不同val也就不同混在一起比较是错的。这就像你同时维护多个窗口每个窗口对应一个起点位置的对角线。这个分组思路是整个优化里最灵性的一步也是正解区别于“用堆优化”的核心所在——堆优化的话你得维护n个堆复杂度是O(mn log n)不如下面的O(mn)。4. 从30分到100分逃过这些坑你才算真正会做这题4.1 环形前缀和的取模细节斜向前缀和sum[t][i] gold[t][i] sum[t-1][(i-1n)%n]这里的(i-1n)%n是为了处理i0时回到n-1的情况。我第一次写成(i-1)%n在C里负数取模的结果是负数直接导致数组越界。这个问题在纯C环境里特别隐蔽因为你可能碰巧没触发崩溃但结果全是错的。我建议你写完前缀和后单独跑一个n3, m3的小样例手算一遍对比程序输出。比如3 3 3 1 2 3 4 5 6 7 8 9 1 1 1 2 2 2 3 3 3手算第一时刻、第二时刻每个位置的斜向前缀和再对照程序基本能排除90%的取模错误。这种“小样例手算验证”的方法做任何环形DP题都适用。4.2 单调队列的弹出顺序先淘汰还是先入队我见过不少人写单调队列时弹出过期元素和插入新元素顺序搞反。直觉上你可能觉得“先插入再淘汰”没问题但这道题的窗口跨度为p如果先插入队首可能是一个刚插入但下标已经过期的元素因为t刚变成j如果p0的话才可能过期但p≥1所以其实先插入问题不大。不过为了稳妥我建议的顺序是先做单调性维护弹出队尾较小值再插入当前元素最后弹出过期元素。为什么这样顺序最稳因为单调性维护会把队列整理成从队首到队尾递减的顺序插入后再弹出过期元素队首一定是窗口内最大且有效的值。如果你先弹出过期再插入逻辑也对但很多人会漏掉“当前元素本身可能过期”的边界情况所以统一用“维护单调性→插入→弹出过期”的顺序可以有效减少心智负担。还有一个细节弹出过期元素时用的是while (!q.empty() q.front() t - p 1)。注意这里比较的是“时间下标”而不是“贡献值”。因为队列里的时间下标是单调递增的我们按时间顺序插入所以队首一定是最早插入的也因此最可能过期。这个“时间下标单调性”是单调队列正确性的基石。4.3 dp数组初始化的陷阱dp[0] 0其余初始化为一个很小的负数比如-0x3f3f3f3f。为什么不能初始化为0因为如果某段时间无论如何都无法到达比如收益为负不得不买机器人但买了更亏那么dp[t]可能保持为负。如果初始化为0你会错误地认为“不行动也行”但题意是每个时间点都强制有机器人运行吗并不——实际上你可以选择不买机器人但那样就没有收益也没有花费所以确实存在“停在原地”的情况吗这里要仔细想题面说的是每个时间点可以买机器人但没说必须买。如果不买那当前时刻就没有机器人捡金币也不需要花钱。所以dp[t]理论上应该保证可以停留在上一个状态也就是dp[t] dp[t-1]。但问题来了如果不买机器人那当前时刻就白白浪费了金币吗其实不是——如果你在更早的时刻买了一个能走P步的机器人它可能覆盖到当前时刻。所以dp[t]的最大值不一定从dp[t-1] 某收益来也可能从dp[t-p] 某收益来甚至从更早来。这正是为什么单调队列要维护长度p的窗口而不是简简单单dp[t] max(dp[t], dp[t-1])。我在代码里没有显式做dp[t] max(dp[t], dp[t-1])因为单调队列窗口长度为pt可以直接从窗口内的任意一个“购买时刻”转移过来所以dp[t-1]如果作为一个购买时刻即t-1时刻买机器人自然会被覆盖。但为了保险我建议你在最后加上dp[t] max(dp[t], dp[t-1])逻辑上更完整也方便排除那些“机器人已经报废但我不买新的”的过渡情况。加上这一行不会影响正确性只可能让某些边界情况更稳。4.4 时间下标和位置下标的统一0-based还是1-based这道题用0-based的位置下标写起来非常方便因为取模运算自然。但用1-based会让金币输入和位置编号更直观。我建议你选定一种就一路用到底不要混用。我的代码里位置用0-based时间用1-based这个组合是最不容易出错的——因为时间有“第0时刻”作为边界位置没有“第0位置”或者说0就是第一个位置混用时容易错位。如果你非要用1-based位置那么取模时要写成((sk-1)%n 1)之类的形式极其容易写错。我自己的经验是动态规划的状态定义尽量用1-based时间0-based位置这样前缀和数组的边界处理最干净环形取模也最不容易错。5. 从这题能带走什么举一反三的思维模型做完P1070我最大的感受是它看起来是个“游戏题”实则是**“带有效期贡献值的状态转移 滑动窗口优化”**的模板题。这类题在竞赛里出现频率极高换汤不换药。比如带冷却时间的技能释放问题每个技能释放后有个冷却是p最大化伤害总值本质上就是维护一个长度为p的窗口内最优技能释放方案。股票买卖问题的一个变种每次交易后必须间隔k天才能再次交易最大化利润同样可以用这个模型。跳格子游戏每次可以跳1到p步每个格子的分数随时间衰减问最大得分——如果“跳的步数”换成“时间间隔”结构和这题几乎一样。所以与其把P1070当作一道孤立的题不如把它抽象成三层认知第一层暴力转移怎么建立。dp[结束时刻] max(历史 本次净收益)这里的核心是搞清楚“一次动作覆盖的时间区间”和“区间收益的计算方式”。第二层怎么把“枚举起点/枚举步数”转化为“枚举购买时刻”。转换视角的关键是发现t和k共同决定结束时刻j这样就可以压缩一维。第三层怎么用单调队列把O(n^2)变成O(n)。单调队列的本质是维护一个“滑动窗口内的最优值”前提是窗口内的值只与插入时刻有关与当前时刻无关。我做题时有个习惯每做完一道题会在题解末尾写一个“思路迁移”小节列出三道同类题或者相关变形题。P1070的迁移清单我列了上面这三条之后遇到类似的题基本能在10分钟之内想到单调队列方案。还有一个小技巧处理这类“环形滑动”的题目可以在纸面上画一个m x n的表格横轴是位置纵轴是时间然后把斜向前缀和的累加路径斜着标出来。这样画一遍比盯代码看得清楚得多。我自己每次写环形DP都会先在草稿纸上画这个表格确认取模方向才动手敲代码。这个习惯帮我避开了无数个“样例过了但WA”的夜晚。6. 最后再分享一个调试技巧对拍程序怎么搭这道题的调试比普通题更麻烦因为环形取模和斜向前缀和单纯靠肉眼根本看不出错在哪。我建议你写一个对拍脚本用暴力版生成答案用正解版生成答案再随机生成小数据跑几千组对比输出。一旦发现不一致立刻缩小数据规模手动分析。我的对拍程序大致这样写写一个gen.cpp随机生成n在1到5、m在1到8、p在1到5的小数据金币和花费都控制在10以内。写一个brute.cpp用最朴素的暴力枚举保证绝对正确。写一个solve.cpp就是正解。用一段脚本循环跑对比brute和solve的输出不一致就打印当前数据和两组输出。这个对拍流程可以帮你快速定位问题出在“前缀和”还是“单调队列”因为你可以在暴力版的循环里加打印逐行对比两个程序在某一个dp[t]处的取值。我通常会在dp更新处打一条printf把t, s, k, sum, val全部打出来跑一两个小数据就能看出来是那个环节错了。如果你第一次接触单调队列优化DP我强烈建议你走完这个流程不要直接跳到提交。做一遍对拍你对这题的理解深度会比看十篇题解都强。P1070是一道“看着简单、写着崩溃、想通后豁然开朗”的题希望这篇题解能帮你少走一些我当年走过的弯路。
阅读完成 · 觉得有帮助？
