P1070道路游戏，最近整理以前的刷题记录时又把它做了一遍。这道题在NOIP2009普及组里算得上压轴题，表面上是个机器人沿环形道路捡金币的游戏，真正的考点却是动态规划优化，而且一考就是两个硬东西：对角线前缀和、单调队列。讨论区里不少人的困惑是“暴力DP能写，但不知道从哪里优化”，这篇就从我自己的做题过程出发，把从朴素DP到最终O(nm)算法的每一步拆开讲。适合正在准备CSP-J/S、NOIP普及组的选手参考，也适合想通过具体题目搞懂DP优化套路的朋友。
1. 先把题意彻底撸清楚
1.1 道路游戏到底在玩什么
有n个工厂围成一个环，相邻工厂之间有n条道路。道路i连接工厂i和工厂i+1，其中最后一条路连接工厂n和工厂1，方向固定，只能沿着编号增大的方向走，绕回1号之后再继续。
游戏持续m个单位时间。每个单位时间里，每条道路都会产生一定数量的金币，产生的数量由输入的m行n列矩阵给出。第i行第j列，就是第i个单位时间内道路j上的金币数量。
游戏里唯一能主动做的操作是买机器人。在任意一个工厂都可以买，每个工厂的机器人价格不同。买完之后，机器人从该工厂出发，沿道路方向前进。每走一条路消耗1个单位时间，同时把这条路上的金币收入囊中。机器人最多连续走p步，走完任意步数后可以在某个工厂停下，停下之后如果想继续刷收益，就在这个工厂再买一个新机器人。
目标很简单：m个单位时间结束的时候，手里的总金币减去买机器人花掉的钱，让这个净值尽量大。
规则里有几个地方容易理解偏。第一，一开始没有机器人，但可以立刻买。第二，机器人不是必须走满p步才能停，走1步、2步，甚至走到p步，都可以停。这直接决定了DP转移时s的范围是一个连续区间。第三，金币是在“经过道路的瞬间”获得的，而不是在每个时间段结束时统一结算，后面实现时下标要对齐。
1.2 状态设计：dp[t]到底表示什么
这类题第一头疼的地方是机器人一直在动，怎么把状态定下来。如果状态里同时带上机器人当前位置、剩余可走步数、当前时间，状态量直接就爆了。
常见的做法是只记录“机器人刚停下”的时刻。定义dp[t]：到第t个时间单位结束的那一刻，机器人刚好在一个工厂停下，手上没有正在运行的机器人时，已经获得的最大净收益。
这里“刚好停下”是关键限定。机器人还在路上跑的状态我们完全不去记录，只记录一段行程结束后的状态。这样t=0就对应游戏还没开始，dp[0]=0。
转移时，考虑最后一次购买机器人的时间点s。在s时刻买完机器人，它从某个工厂k出发，连续走t-s步，在t时刻停下。因为机器人走的步数必须在1到p之间，所以s的取值只能是[max(0, t-p), t-1]。
转移方程写作：
dp[t] = max over s, k of ( dp[s] - cost[k] + 某段路径的金币总和 )
dp[s]是s时刻空闲时的最大收益，这时候买一台新机器人，先扣掉价格cost[k]，再把它这一趟赚到的金币全部加上，就得到新状态。这个转移把“买机器人”这个动作放在s时刻，子问题和原问题的结构完全一致，所以DP是正确的。
1.3 朴素DP的复杂度
如果直接按上面的枚举来，内层把一段路径的金币用循环累加，复杂度大约是O(m^2 * n * p)级别。就算先预处理任意时间区间、任意起点、任意长度这段路径的金币总和，也需要枚举t、s、k三个变量，复杂度是O(m * n * p)。
本题数据范围n、m、p都能到1000，O(10^9)次运算在普通评测机上必然超时。所以必须同时优化“金币段求和”和“枚举维度”这两件事。
2. 优化第一步：用对角线前缀和把金币累加变成O(1)
2.1 机器人路径里藏着一个不变量
先把所有下标统一改成从0开始。假设机器人在时刻s从工厂k出发，它走的第1步对应时间段s，走过的道路是k；第2步对应时间段s+1，走过的道路是(k+1) mod n；一般地，第r步对应时间段s+r-1，走过的道路是(k+r-1) mod n。
观察一下道路编号和时间段编号之间的关系：
road ≡ k + (time - s) (mod n)
稍微移项就变成：
road - time ≡ k - s (mod n)
也就是说，机器人一整段行程经过的所有格子，在“时间段-道路编号”这个二维矩阵里，始终满足road - time等于同一个常数。这个常数由出发工厂k和购买时刻s共同决定。
这个性质可以这样理解：时间往前走一个单位，道路编号也同步往前走一格，两者的相对位置永远锁定。我们把锁定的这个相位值记作id：
id = (k - s) mod n
于是，任意一段合法的机器人路径，整条路径都落在同一条“副对角线”上。这句话是整个优化的核心，后面所有工作都是围绕它展开的。
2.2 给每条对角线单独做前缀和
既然路径可以落到固定对角线上，那就可以按对角线来累加金币。
定义S[id][t]为：第id条对角线上，从第0个时间段到第t-1个时间段的金币总和。预处理方法很直接：
S[id][0] = 0 S[id][t] = S[id][t-1] + coins[t-1][(t-1+id) mod n]
这里coins是0-based输入矩阵，coins[i][j]表示第i个时间段道路j上的金币。因为对角线上满足road - time ≡ id，所以第time行要取的列就是(time + id) mod n。
举个例子，如果id=1，那么时间段0取道路1，时间段1取道路2，时间段2取道路3，依次类推，循环绕回。这个预处理是O(nm)的，完全可以接受。
有了S之后，从s时刻出发、走到t时刻停下的机器人，捡到的金币总和就是：
S[id][t] - S[id][s]
注意这里不需要再关心机器人到底是从哪个工厂出发的，只要id确定了，路径上的金币总和就确定了，因为id已经同时蕴含了起点工厂和购买时刻。
2.3 用前缀和改写转移方程
把原来的求和换成前缀和差，转移方程变成：
dp[t] = max of ( dp[s] - cost[k] + S[id][t] - S[id][s] )
其中 id = (k - s) mod n。
到这一步仍然有三个枚举量t、s、k。但有一个关键观察：id和k不是两个独立变量。给定s和id，k被唯一确定：
k = (s + id) mod n
所以完全可以把枚举k改成枚举id。方程变成：
dp[t] = max of ( dp[s] - cost[(s+id) mod n] - S[id][s] ) + S[id][t]
外层中括号里的部分只和s、id有关，S[id][t]只和id、t有关。这看起来只是换了个枚举对象，真正的质变发生在下一步：把id固定住，对每个id单独维护一个随t滑动的最大值。
为什么要反过来枚举id而不是枚举k？因为如果枚举k，id由k和s共同决定，同一个id会被重复访问很多次，前缀和的连续性发挥不出来。反过来枚举id，k由s和id直接算出，id维度就能独立处理。
3. 优化第二步：用单调队列把枚举维度压下来
3.1 问题变成了定长滑动窗口最大值
固定一个id，定义辅助数组：
val[id][s] = dp[s] - cost[(s+id) mod n] - S[id][s]
那么转移方程里，对当前t需要用到的就是：
max( val[id][s] ) + S[id][t]
其中s必须落在区间[t-p, t-1]内。
这是非常标准的定长滑动窗口最大值问题。窗口的左端和右端都随着t单调向右移动，并且每次只移动一格。用大根堆配合懒惰删除也能做，但单调队列更合适：每个元素最多进队一次、出队一次，均摊O(1)，且代码量很小。
这里必须强调一个容易误解的点：不是所有id共用一个队列，而是每个id维护自己独立的单调队列。因为val[id][s]和S[id][t]都跟id绑定，id不同，序列完全不同，混在一起会破坏单调性。
3.2 队列里存下标，按值单调递减
对每个id维护一个队列，队列里存的是下标s，而不是值本身。队列内部按val[id][s]从大到小排列，队首始终是当前窗口内最优的下标。
插入新元素s时，从队尾往前检查，把所有val值不大于当前新元素的旧元素全部弹出。这些旧元素既更老，又不比新元素优，以后不可能成为最大值，留着只会增加查询成本。
弹出过期元素时，只看队首。因为所有下标都是从小到大依次入队的，且单调队列从队尾插入、队尾弹出，并不会破坏下标从左到右递增的性质。队首的下标如果小于当前窗口左端t-p，说明它已经跑出窗口，直接让头指针往后移。
查询时，队首就是答案。
3.3 整体流程和入队时机
算法按t从1到m顺序处理：
- 对每个id，把队列中所有下标小于t-p的元素弹出。
- 对每个id，如果队列非空，用队首的val[id][s]加上S[id][t]更新dp[t]。
- 用刚算出的dp[t]生成val[id][t]，对每个id插入对应队列，供后续t使用。
计算顺序非常关键：一定是先更新dp[t]，再把下标t入队。如果顺序反了，就会出现s等于t的转移，相当于机器人走了0步，这是不合法的。
初始化的细节也要注意。游戏最开始时s=0，dp[0]=0，所以s=0的val值要在主循环开始前插入所有id的队列。val[id][0] = 0 - cost[(0+id) mod n] - 0 = -cost[id]，正好对应“一开始就买个机器人出发”的决策。
复杂度方面，每个id的每个下标最多入队一次、出队一次，整体O(nm)。相比朴素DP的O(mnp)，这是一次数量级的压缩。对n=m=p=1000的数据来说，优化后只需要跑大约一百万次操作，非常轻松。
4. 完整实现与容易翻车的细节
4.1 一份能AC的参考代码
下面这份代码是完整的C++实现。数组大小开到1005，因为n、m最大都是1000。
#include <bits/stdc++.h> using namespace std; const int N = 1005; const int INF = 0x3f3f3f3f; int n, m, p; int coins[N][N]; // 0-based: coins[time][road] int cost[N]; // 0-based: 工厂i的机器人价格 int S[N][N]; // S[id][t]: 对角线id上，时间段[0,t)的金币总和 int dp[N]; // dp[t]: 时间t结束时刚好停车的最大收益 int val[N][N]; // val[id][s]: 单调队列排序用的辅助值 int q[N][N]; // 每个id一个单调队列，存下标 int head[N], tail[N]; int main() { scanf("%d%d%d", &n, &m, &p); for (int i = 0; i < m; ++i) for (int j = 0; j < n; ++j) scanf("%d", &coins[i][j]); for (int i = 0; i < n; ++i) scanf("%d", &cost[i]); // 对角线前缀和 for (int id = 0; id < n; ++id) { S[id][0] = 0; for (int t = 1; t <= m; ++t) S[id][t] = S[id][t - 1] + coins[t - 1][(t - 1 + id) % n]; } dp[0] = 0; // 初始化：把s=0放进所有id的队列 for (int id = 0; id < n; ++id) { head[id] = tail[id] = 0; val[id][0] = dp[0] - cost[(0 + id) % n] - S[id][0]; q[id][tail[id]++] = 0; } for (int t = 1; t <= m; ++t) { // 弹出过期下标 s < t-p for (int id = 0; id < n; ++id) { while (head[id] < tail[id] && q[id][head[id]] < t - p) ++head[id]; } // 用每个id的队首更新dp[t] dp[t] = -INF; for (int id = 0; id < n; ++id) { if (head[id] < tail[id]) { int s = q[id][head[id]]; dp[t] = max(dp[t], val[id][s] + S[id][t]); } } // t=m时不再入队，因为s=m不会再被用作购买时刻 if (t == m) break; // 用dp[t]生成val[id][t]并入队 for (int id = 0; id < n; ++id) { val[id][t] = dp[t] - cost[(t + id) % n] - S[id][t]; while (head[id] < tail[id]) { int last = q[id][tail[id] - 1]; if (val[id][last] <= val[id][t]) --tail[id]; else break; } q[id][tail[id]++] = t; } } printf("%d\n", max(0, dp[m])); return 0; }4.2 四个高频翻车点
第一个是下标体系混乱。题目给的是1-based输入，代码里全转成0-based之后，S的列索引必须写成(t-1+id)%n，不能写成(t+id)%n。这个错位会让时间维整体差1，查起来非常隐蔽。
第二个是入队时机。val[id][t]必须在dp[t]更新完之后再算，并且t=m时不能入队。虽然t=m之后再没有查询了，但从语义上说，s=m不可能再作为购买时刻出现，留着一个非法状态总归是个隐患。
第三个是过期判断。窗口左端是t-p，所以队首下标小于t-p才需要弹出。如果把小于写成小于等于，会把刚好合法的s=t-p也弹出去，导致答案偏小。
第四个是负数取模。C++里取模对负数会截断向零，比如(-1)%5结果是-1。如果某处非要写(road-time)%n这类式子，记得先加n再取模。更简单的做法是像代码里这样，从id反推k，保证模运算里永远不出现负数。
4.3 手工验证一个最小样例
用一个最小的例子把算法流程走一遍。假设n=2、m=3、p=2，金币矩阵为：
| 时间段 | 道路1 | 道路2 |
|---|---|---|
| 1 | 1 | 2 |
| 2 | 3 | 4 |
| 3 | 5 | 6 |
两个工厂的机器人价格都是1。
手工推dp：
dp[0] = 0。
dp[1]：只能从s=0走1步。从工厂0出发捡1，扣1，净0；从工厂1出发捡2，扣1，净1。所以dp[1]=1。
dp[2]：s可以取0或1。s=0走2步时，从工厂0出发捡1+4=5，扣1，净4；从工厂1出发捡2+3=5，扣1，净4。s=1走1步时，dp[1]=1，从工厂1出发捡4，扣1，净4。所以dp[2]=4。
dp[3]：s可以取1或2。s=1走2步，从工厂0出发捡3+6=9，加上dp[1]=1再扣1，净9；从工厂1出发捡4+5=9，同样净9。s=2走1步，dp[2]=4，从工厂1出发捡6，扣1，净9。所以dp[3]=9。
最终答案是9。这个结果用上面的代码跑也是一样的，建议大家自己动手对一遍。
5. 常见问题与调试技巧实录
5.1 答案为什么要和0取max
有些数据里所有金币收益都很低，机器人价格又高，最优策略其实是什么都不做，最后收益是0。但dp[m]的定义强制要求“在m时刻刚好停了一台机器人”，这时算出dp[m]很可能是负数。所以最后输出max(0, dp[m])才稳妥。原题部分测试点可能本身就不会出现负答案，但加上这个判断完全没有成本。
5.2 单调队列的过期元素清不干净怎么办
单调队列里有一个重要的性质：由于下标是按s从小到大依次插入，且只从队尾插入、队尾弹出，队列里的下标从左到右必然单调递增。所以过期元素只可能出现在队首，不可能藏在队列中间。
如果某次运行结果偏大，优先检查两件事：一是弹出过期的while条件是不是漏写了；二是head指针有没有误写成tail指针。这两个都是实际调试时遇到过的坑。
5.3 初始化队列的时机
有人会把s=0的插入操作放在t循环里面做，比如在t=1时才插入s=0。这样勉强能出结果，但后续t增大时很容易忘记这个初始元素的存在，导致窗口里缺少早期下标。不如在主循环前一次性把所有id的s=0都插入，逻辑更统一。
同样，每次更新完dp[t]后，要记得把s=t插入队列，保证后面的窗口里有足够的新元素。漏掉这一步的话，t稍大一点队列就空了，dp[t]会一直停在负无穷。
5.4 内存和代码结构的建议
N开到1005，四个二维数组coins、S、val、q都是1005乘1005的int，总占用大约16MB，内存限制通常完全够用。不过大数组一定要放在全局区，不要在函数内部开，否则容易爆栈。
如果将来想改写成动态分配内存的版本，可以把S和val按id逐行分配vector，q用deque实现。但本题数据范围很小，数组写法最简单直接。
5.5 对拍是个好习惯
这种优化DP最容易出的问题不是思路错，而是细节差一点。我的建议是写优化版之前先写一版暴力DP，哪怕只用来对拍。暴力版可以帮我验证题意和转移方程完全理解正确，优化版出问题时也有参照物。
本题的暴力版很短，枚举t、s、k然后累加金币就行。随机生成小数据后暴力跑一遍、优化版跑一遍，结果不一致就打印队列调试。实测下来，这个流程能省去大量瞎改的时间。
5.6 从这道题里提炼出的通用套路
做完这道题最大的收获是识别“不变量”的思路。以后再遇到环形地图加时间推进的题目，可以先想想：在时间变大的过程中，有没有某个量是保持不变的？比如这里的道路编号减时间编号始终固定。一旦找到这个量，空间维度和时间维度就可能被解耦，前缀和和滑动窗口这类工具就能用上。
另外，如果状态转移里出现“当前时刻减去某个过去时刻必须落在固定区间”的限制，大概率就是滑动窗口优化的信号。这时候把一个枚举维度提前分离出来，往往能收到奇效。
最后再分享一个我个人很受用的习惯：优化DP时先把数学式子写到最简，再开始翻译代码。很多人一上来就改代码，结果越改越乱。把式子里的每个下标含义标注清楚，写代码时其实是看着式子抄一遍，正确率会高很多。P1070这题，只要抓住了对角线不变性和单调队列入队时机，AC就只是时间问题。
