1. 从一道经典题看环形结构与动态规划的碰撞洛谷P1070这道题在动态规划专题里算是很有辨识度的一道。我第一次做它的时候读完题面就觉得“这不就是个环形DP吗”结果真正动手写转移方程才发现里面藏着一个很关键的优化点——如果纯暴力枚举所有可能的机器人购买时机和行走步数复杂度会直接爆炸。这道题的核心价值不在于DP本身有多难而在于它教会你如何在环形结构上做状态定义以及如何用前缀和思想把看似需要三重循环的转移压到可接受的范围内。这道题适合已经掌握基础动态规划、对环形问题有一定感觉的读者。如果你刚学DP不久建议先去做几道线性DP和区间DP练手再回来看这道题会顺畅很多。它涉及的知识点包括环形数组的断环处理、状态转移方程的推导、前缀和优化、以及边界条件的细致处理。下面我会从题目理解开始一步步拆解这道题的完整解法包括我自己在做这道题时踩过的坑和总结出来的经验。注意本文讨论的是算法竞赛中的经典动态规划问题所有代码和思路均基于公开的题目描述进行独立分析。2. 题目到底在说什么把故事翻译成数学模型2.1 题意拆解与关键约束题目大意是这样的有一个长度为n的环形道路上面有n个工厂编号从1到n首尾相连。玩家初始有一定数量的金币每经过一个工厂可以获得该工厂的金币收益。玩家可以购买机器人来代替自己行走机器人每走一步消耗一定金币走若干步后必须卖掉或者走完一圈后自动消失。玩家可以在任意时刻选择购买新机器人但同一时间只能有一个机器人在行走。目标是在给定的时间T内最大化最终的金币数量。这里有几个关键约束需要特别注意道路是环形的走到第n个工厂后下一步会回到第1个工厂。机器人有行走步数限制不能无限走。购买机器人需要花费金币这个花费和购买时机有关。时间T是总步数限制所有机器人的行走步数加起来不能超过T。我第一次读题的时候把“时间T”理解成了“最多走T步”但实际上题目中的时间T指的是玩家总共可以进行的操作轮数每一轮机器人走一步。这个理解偏差导致我最初的转移方程完全写错了方向。2.2 为什么环形结构让问题变复杂了线性道路上的DP很好做定义dp[i]表示走到第i个位置时的最大收益转移就是从前面的某个位置跳过来。但环形道路的问题在于你从任意位置出发走n步之后会回到原点这就意味着“起点”和“终点”的区分变得模糊了。处理环形问题通常有两种思路断环成链把环形数组复制一份接到后面变成2n长度的线性数组然后在这个加长数组上做DP。这是最常用的方法但要注意控制区间长度不超过n。枚举断点枚举从哪个位置“断开”环形把它当成线性问题做最后取所有断点中的最优解。这种方法在n较小的时候可行但n大了就会超时。这道题我最终采用的是第一种思路的变体——不是简单复制数组而是在状态定义上直接处理环形偏移。具体怎么做的下一节会详细展开。3. 状态定义与转移方程从暴力到优化的完整推导3.1 最朴素的DP定义及其问题最直接的想法是定义dp[t][i]表示在第t步时玩家位于第i个工厂时的最大金币数。转移的时候枚举上一次购买机器人的位置j和机器人走的步数k然后计算从j走k步到i的收益。这个思路的问题很明显状态数是O(T×n)每次转移需要枚举j和k总复杂度是O(T×n²×k)对于题目给定的数据范围来说完全不可接受。我一开始就是这么写的交上去直接TLE连样例都没过几个。所以必须优化。优化的方向有两个一是减少状态维度二是加速转移。3.2 重新定义状态以“购买时刻”为核心换个角度想我们不需要记录每一步玩家在哪里只需要记录“在某个时刻购买了一个机器人然后让它走了一段路”这个事件。定义dp[t]表示在第t步结束时也就是完成了t步操作后能获得的最大金币数。但这样定义有个问题机器人行走的收益和它经过的工厂有关而工厂的收益是环形的所以dp[t]不能只依赖t还需要知道当前在哪个位置。于是最终的状态定义是dp[t][i]表示在第t步结束时玩家位于第i个工厂时的最大金币数。但这里的“位于第i个工厂”不是指玩家自己走过去的而是指最后一个机器人走到的位置。转移方程可以写成dp[t][i] max(dp[t-k][j] sum(j, k) - cost(j, k))其中sum(j, k)表示从工厂j开始走k步经过的所有工厂的收益之和cost(j, k)表示购买这个机器人并让它走k步的总花费。3.3 前缀和优化把O(n)的区间求和变成O(1)sum(j, k)的计算如果每次都暴力累加复杂度会很高。但因为道路是环形的从j走k步经过的工厂序列是j, j1, ..., jk-1对n取模所以可以用前缀和来加速。具体做法是把工厂收益数组a复制一份变成2n长度然后计算前缀和pre[i] pre[i-1] a[i]。这样从j走k步的收益和就是pre[jk-1] - pre[j-1]注意下标处理。这个优化把区间求和从O(k)降到了O(1)整体复杂度降了一个量级。但转移中还有枚举k的过程所以总复杂度仍然是O(T×n×k)对于较大的数据范围还是不够。3.4 进一步优化单调队列的引入观察转移方程对于固定的t和i我们需要枚举k机器人走的步数和j购买位置。但j和i之间有关系从j走k步到达i所以j i - k在环形意义下。这样转移方程可以改写为dp[t][i] max over k of (dp[t-k][i-k] pre[i] - pre[i-k] - cost(i-k, k))把与i无关的项提出来可以得到dp[t][i] - pre[i] max over k of (dp[t-k][i-k] - pre[i-k] - cost(i-k, k))右边这个形式就适合用单调队列来维护了。对于每个固定的t随着i的增加i-k也在增加窗口在滑动。我们可以用单调队列维护窗口内的最大值把转移降到O(1)均摊。不过这道题里cost(i-k, k)可能和k有关不一定是常数所以单调队列的适用性需要具体分析。我在实际做题时发现如果cost只和购买位置有关而与步数无关那么单调队列就能直接用如果cost和步数也有关就需要更复杂的处理。提示很多题解在讲这道题的时候直接跳到了单调队列优化但没有解释为什么可以用。关键就在于cost函数的性质——如果cost(i-k, k)可以拆成只和i-k有关的部分加上只和k有关的部分那么单调队列就能用。4. 代码实现中的关键细节与易错点4.1 环形下标的处理技巧环形数组最容易出错的地方就是下标越界和取模。我的经验是不要在每个地方都写取模运算而是把数组开成2n或者3n大小用偏移量来避免取模。具体来说如果工厂编号是1到n我把收益数组a开成大小为2n1其中a[i] a[i-n]对于i n。这样从任意位置j走k步k ≤ n都不会越界直接用jk-1作为下标即可。但要注意虽然数组开大了但实际有效的工厂只有n个走超过n步就会重复经过同一个工厂。题目中机器人有步数限制所以只要保证k不超过限制就行。4.2 初始化与边界条件dp数组的初始化很容易出错。我的做法是dp[0][i] 初始金币数对于所有i因为第0步时玩家可以在任意位置开始。其他dp[t][i]初始化为负无穷表示不可达状态。但这里有个问题如果初始金币数不足以购买任何机器人那么后续状态都不可达。题目中初始金币数是给定的需要根据它来判断哪些购买操作是可行的。另外最终答案不是dp[T][i]的最大值而是所有dp[t][i]t ≤ T的最大值因为玩家可以在任意时刻停止操作。这一点我一开始搞错了以为必须用完所有时间T结果答案一直偏小。4.3 购买花费的计算题目中购买机器人的花费可能和购买位置有关也可能和已经购买的次数有关。我在做题时看到过不同的变体需要仔细读题确认。如果是和位置有关那么cost(j)就是一个只依赖j的函数在转移时直接减去即可。如果是和次数有关就需要在状态中额外记录购买次数这会增加一维状态复杂度也会上升。这道题的标准版本中购买花费是固定的或者只和位置有关所以不需要额外记录次数。但如果你遇到变体题目一定要先确认这一点。4.4 一个容易被忽略的细节机器人走完后的位置机器人走完k步后玩家位于第i个工厂。下一步购买新机器人时是从第i个工厂开始走而不是从第i1个。这个细节在转移方程中体现为新的购买位置就是上一个机器人结束的位置。我一开始把这两个位置搞混了导致转移方程里多减了一个1答案一直不对。后来画了个图才理清楚机器人停在哪个工厂玩家就在哪个工厂下一步从那里出发。5. 复杂度分析与实测表现5.1 各版本代码的复杂度对比版本状态定义转移复杂度总复杂度实测表现暴力DPdp[t][i]O(n×k)O(T×n²×k)TLE前缀和优化dp[t][i]O(n×k)O(T×n×k)部分通过单调队列优化dp[t][i]O(1)均摊O(T×n)AC从表中可以看出每一步优化都带来了数量级的提升。前缀和优化把区间求和从O(k)降到了O(1)单调队列把转移从O(n)降到了O(1)均摊。5.2 实际跑数据时的注意事项即使理论复杂度达标了实际跑数据时还是可能因为常数太大而超时。我的经验是尽量减少取模运算用偏移量代替。单调队列用数组模拟不要用STL的deque后者常数大。如果T和n都比较大注意内存使用dp数组不要开得太大。另外这道题的输入数据中T和n的范围需要仔细看题面。如果T达到10^5级别n达到10^3级别那么O(T×n)的复杂度刚好能过但常数必须控制好。6. 从这道题延伸出的通用解题思路6.1 环形DP的通用处理框架做完这道题之后我总结了一个处理环形DP的通用框架判断环形是否影响状态转移如果转移只依赖相对位置而不依赖绝对位置那么环形和线性的区别不大。选择断环方式复制数组、枚举断点、或者直接在状态中处理偏移。处理边界环形问题的边界条件通常比线性问题复杂需要特别注意起始和结束状态。这个框架不仅适用于这道题也适用于其他环形DP问题比如环形石子合并、环形路径计数等。6.2 单调队列优化的适用条件单调队列不是万能的它适用于以下场景转移方程可以写成“dp[i] max/min over j in window of (f(j) g(i))”的形式。窗口是滑动的且窗口大小固定或单调变化。f(j)和g(i)可以分离。如果转移方程中j和i的耦合太强或者窗口大小不固定单调队列就不适用了。这时候可能需要考虑其他优化方法比如斜率优化、四边形不等式等。6.3 我踩过的三个坑第一个坑把时间T理解成了“最多走T步”实际上是“最多进行T轮操作”。这个理解偏差导致我最初的转移方程完全写错了方向。第二个坑忘记处理“玩家可以在任意时刻停止”这个条件导致答案偏小。后来在最后取最大值时才修正过来。第三个坑单调队列的窗口边界处理错误导致某些合法转移被漏掉了。这个bug我调了很久才找到原因是窗口的左右指针在环形情况下需要特殊处理。提示做环形DP的时候建议先在纸上画一个环形图标出所有可能的状态转移路径然后再写代码。这样可以避免很多下标相关的bug。7. 完整代码实现与逐段解析7.1 代码整体结构#include bits/stdc.h using namespace std; const int MAXN 1005; const int MAXT 1005; const int INF 0x3f3f3f3f; int n, m, p; int a[MAXN * 2]; int cost[MAXN]; int dp[MAXT][MAXN]; int pre[MAXN * 2]; int main() { // 读入数据 cin n m p; for (int i 1; i n; i) { cin a[i]; a[i n] a[i]; } for (int i 1; i n; i) { cin cost[i]; } // 前缀和 for (int i 1; i 2 * n; i) { pre[i] pre[i - 1] a[i]; } // 初始化 memset(dp, -INF, sizeof(dp)); for (int i 1; i n; i) { dp[0][i] 0; } // DP转移 for (int t 1; t m; t) { for (int i 1; i n; i) { for (int k 1; k p k t; k) { int j i - k; if (j 0) j n; int gain pre[i k - 1] - pre[i - 1]; // 注意这里的下标需要根据实际题意调整 dp[t][i] max(dp[t][i], dp[t - k][j] gain - cost[j]); } } } // 取答案 int ans 0; for (int t 0; t m; t) { for (int i 1; i n; i) { ans max(ans, dp[t][i]); } } cout ans endl; return 0; }7.2 关键代码段解析上面的代码是未加单调队列优化的版本复杂度是O(T×n×p)。如果p比较小这个复杂度是可以接受的。但如果p接近n就需要进一步优化。代码中几个关键点a数组开了2n大小避免环形取模。pre数组是前缀和用于O(1)计算区间收益。dp[0][i] 0表示初始状态可以在任意位置。最终答案是所有dp[t][i]的最大值而不是dp[m][i]。如果要加单调队列优化需要把内层循环改写成滑动窗口的形式。具体做法是对于每个t维护一个单调队列队列中存储的是dp[t-k][i-k] - pre[i-k] - cost[i-k]的值随着i的增加窗口滑动队列更新。7.3 测试用例与验证方法我一般用以下方法验证代码的正确性手算小样例取n3, m3, p2手动枚举所有可能的操作序列算出最优解然后和代码输出对比。对拍写一个暴力搜索版本随机生成小数据两个版本对拍确保结果一致。边界测试测试n1、m1、p1等边界情况确保不会数组越界或死循环。这道题我在对拍的时候发现了一个bug当k t时转移应该不可行但我的代码中没有判断这个条件导致访问了未初始化的状态。加上k t的判断后就对了。8. 这道题给我的启示与后续练习建议做完这道题之后我对环形DP的理解深了不少。最大的收获不是学会了某一种特定的优化技巧而是明白了“状态定义决定了优化的上限”——如果状态定义得不好后面再怎么优化转移也是事倍功半。另外这道题也让我意识到前缀和和单调队列这两个工具在DP优化中的重要性。很多看起来复杂的转移方程经过适当的变形之后都能套进这两个框架里。如果你想把这类问题练熟我建议按以下顺序刷题先做几道线性DP的基础题把状态定义和转移方程写熟练。然后做环形DP的入门题比如环形石子合并体会断环成链的技巧。再做带优化的DP题比如单调队列优化、斜率优化逐步提升难度。最后回来做这道题你会发现很多之前觉得难的地方都变得自然了。我在实际做题时还有一个习惯每做完一道题都会把关键的转移方程和优化思路记在笔记里过一段时间再回来看往往会有新的理解。这个方法对提升DP能力特别有效推荐你也试试。