1. 题目到底在考什么从渡轮场景中抽象出DP模型做过的DP题不算少但每次碰到“轮船问题”这种带调度味道的题目第一反应还是容易往贪心上想船到了就拉拉满就走能走一辆是一辆。真这么写小样例能过数据一大就WA得莫名其妙。后来把这道codevs 1620反复推了几遍才弄清楚它本质上一个带时间窗约束的调度DP贪心失效的点恰恰藏在“等还是不等”这个决策里。这类题的第一道坎是建模。题目表面是模拟渡轮来回装车但真正要你求的是“在满足每辆车等待时间上限的前提下最多能运走多少辆车”。所有车按到达顺序排好船每趟从本岸出发开到对岸再返回往返一个周期固定为2T每次发船最多装C辆每辆车从到达那一刻开始计时等待超过W就会自动离开不再参与后续装载。目标很简单就是最大化最终上船的车数。为什么不能直接模拟因为船什么时刻发船是一个可以人为控制的决策变量。你提前发船早到的车确实不会被拒但可能这一趟只装了一两辆船回来得早也接不了下一批你故意往后拖等到后面一大批车都到了再发船虽然早到的车可能因为等待超时被放弃但一趟能装满C辆总装载量反而更大。这个权衡就是DP的切入点。这道题还有两个隐藏的坑。第一个是车的到达时间严格递增所有车必须按到达顺序被服务船不能越过排在前面没处理的车去装后面的车。第二个是“等待超时”的判定在时间轴上是单调的——如果某辆车在时刻d还没超时那它后面所有比它晚到的车在时刻d也一定还没超时反过来如果第k辆车在时刻d已经超时被拒那它前面的车在d时刻必然也全部超时了。这个单调性非常关键它保证了每艘船实际装走的车在原始序列中一定是一段连续区间中间不会出现“装一辆、跳一辆、再装一辆”的交叉情况。用一句话总结把“每辆车的去留”翻译成“若干艘船各自装走原序列中的某一段”段与段之间可以有空隙空隙里的车都是在对应发船时刻已经等待超时的弃子。剩下的工作就是设计状态把这个分段决策用DP串起来。2. 状态设计与转移方程推导2.1 状态定义别用“前i辆车”一笔带过很多新手写这道题喜欢直接定义 f[i] 表示“前i辆车处理完后的最大装载数”然后枚举一辆辆车上不上船。这个思路在这个题目里走不通因为船的发船时间会直接影响后续所有车辆的命运而装载数本身并不携带时间信息。同一个f[i]对应的可能是一艘早发船的方案也可能是一艘晚发船的方案两者的后续扩展能力完全不同。我的做法是给状态加一个约束dp[i] 表示“第i辆车被某艘船装载并且它是这艘船装走的最后一辆车”时当前能达到的最优状态。最优状态用一个二元组 (cnt, time) 描述cnt表示到第i辆车为止总共装载的数量time表示这艘船从本岸出发的时刻。因为第i辆是这个船次的末尾所以time也是这艘船离开本岸的时刻。为什么必须限定“最后一辆”因为转移的时候我们需要知道上一艘船装到了哪个位置、什么时候发的船才能推算下一艘船最早什么时候能回到本岸、什么时候能再次发船。如果状态里不知道上艘船装到哪辆车就没法判断空隙里那些车到底是被拒了还是在等待。这个“末尾约束”是这类分段调度DP的通用技巧。初始化时dp[0] 表示“还没有任何船出发”cnt 0time 0船就在本岸待命。注意这个0号状态很特殊它和 j 0 的普通状态在转移时处理方式不一样后面代码里会专门说明。2.2 转移条件逐个拆解假设当前状态从 dp[j] 转移过来第j辆车是上一艘船装走的最后一辆现在要枚举下一艘船装走的连续区间 [l, i]其中l是这艘船装走的第一辆车i是最后一辆车。整个转移需要同时满足下面几个条件。第一个是容量条件段长不能超过船的最大载车数i - l 1 C。这没什么好说的船一次最多装C辆。第二个是发船时刻的推算。如果 j 0说明这是第一艘船船最初就在本岸最早可发船时刻 ready 0如果 j 0上一艘船在 time[j] 时刻出发经过一个往返周期 2T 才能回到本岸所以 ready time[j] 2T。当前这艘船要等第一辆装载车l到达因此最早发船时刻 d max(ready, a[l])。第三个是等待时间约束。第l辆车是当前船段里最早到达的它的等待时间一定最长只要它没超时后面的 i - l 辆车也不可能超时所以 d a[l] W 必须成立。这个条件可以一次性覆盖整个连续区间。第四个条件最容易被忽略如果 l j 1说明上一艘船和当前船之间存在空隙车辆区间 [j1, l-1] 里的车既没有在上艘船被装走也不在当前船装载范围内。它们要成为弃子必须是在当前船发船时刻d之前已经等待超时并且离开了队列。由于第 l-1 辆车是这些空隙车里最晚到达的它最不容易超时只要它满足 d a[l-1] W前面所有空隙车就都满足。这一步是整个转移的合法性保障少了它DP会偷偷“跳车”算出不合法的结果。当所有条件满足时就可以得到新的状态new_cnt dp[j].cnt (i - l 1)new_time d用这个状态去更新 dp[i]。因为同一个 i 可能来自多种不同的 j 和 l 组合需要保留最终的非支配解。2.3 为什么答案取 max(dp[i]) 而不是 dp[n]这个问题我当时纠结了很久。最后处理到第n辆车为什么不等于直接输出 dp[n].cnt原因很简单dp[n] 要求第n辆车必须被某艘船装载但最优解里第n辆车完全可能因为晚到或者等待超时被放弃。比如所有车到达时间很密集最后一辆到达时码头已经因为船周期和容量限制没法再装它它最终被拒但前面所有车都成功过河了。这种情况下最优装载目标里的“最后一个被装载的车”可能是第n-1辆而不是第n辆。更准确地说dp[i] 表示“处理完前i辆车并且第i辆被装走”这个约束下的最优值答案应该遍历所有可能的“最后被装载车辆”取最大的cnt。至于第i辆之后那些没被处理的车它们最终要么在后续某次发船时超时被拒要么一直等到超过W自然离开这些都不会增加装载数量也不会让已经装走的车数量减少所以不影响答案的统计。这个“答案取max而不是取dp[n]”的细节在很多序列DP里都会出现。凡是状态定义里带“末尾元素必须做某事”这种强约束的最后都要记得枚举末尾位置不能默认最后一个元素一定要参与。3. 完整实现与关键代码注释3.1 C 代码O(n^3) 基础版下面这份代码是我按照上面推导思路写的。为了把转移逻辑讲清楚我保留了最朴素的写法没有做任何优化代码可读性优先。#include bits/stdc.h using namespace std; const int INF 0x3f3f3f3f; const int MAXN 505; struct State { int cnt; // 到当前状态为止总共装载的车数 int time; // 当前这艘船发船的时刻 State() : cnt(-1), time(INF) {} }; int n, T, C, W; int a[MAXN]; State dp[MAXN]; // 尝试用 (cnt, time) 更新 dp[idx] void update(int idx, int cnt, int time) { if (cnt dp[idx].cnt || (cnt dp[idx].cnt time dp[idx].time)) { dp[idx].cnt cnt; dp[idx].time time; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cin n T C W; for (int i 1; i n; i) cin a[i]; dp[0].cnt 0; dp[0].time 0; for (int i 1; i n; i) { // 枚举上一艘船装走的最后一辆车 j for (int j 0; j i; j) { if (dp[j].cnt -1) continue; // 枚举当前这艘船装走的第一辆车 l for (int l j 1; l i; l) { int len i - l 1; if (len C) continue; // 船最早能发船的时刻 int ready (j 0 ? 0 : dp[j].time 2 * T); int d max(ready, a[l]); // 第l辆车是当前段内最早到达的等待时间最长 if (d a[l] W) continue; // 如果 l 和 j1 之间有被跳过的车这些车必须在 d 时刻之前全部超时 if (l j 1) { if (d a[l - 1] W) continue; } int new_cnt dp[j].cnt len; update(i, new_cnt, d); } } } int ans 0; for (int i 1; i n; i) { ans max(ans, dp[i].cnt); } cout ans endl; return 0; }这段代码的核心在两层转移循环里。外层枚举当前船段的末尾 i中层枚举上一艘船的末尾 j内层枚举当前船段的起点 l。三层循环虽然看起来暴力但每一层都有严格的物理含义j决定上一艘船装到哪l决定当前船从哪开始装i决定当前船装到哪结束。初始化时我把 dp[0].time 设为0含义是“第0辆车处理完、船在本岸待命”。这个0号状态和普通状态的区别在第一艘船的 ready 计算里体现第一艘船不用等船回来所以在 j0 时直接令 ready0而不是 dp[0].time 2T。3.2 复杂度分析数据范围决定写法这个版本的时间复杂度是 O(n^3)空间复杂度 O(n)。如果 n 在200左右跑起来毫无压力n到500也勉强能接受一旦 n 到1000以上最坏情况的三层循环就要跑10亿次基本必超时。实际写题的时候我一般先看题目给的数据范围再决定写法。n 200直接上面这份代码交n 1000需要优化掉一层循环n 10000那必须另找更线性的做法。优化方向主要有两个。第一个是预处理 next 数组对于每个起点 l在给定船就绪时刻的情况下最多能连续装到哪个位置这样内层就不用枚举 i。第二个是用数据结构维护前缀信息把枚举 j 和 l 两层循环压成一层。不过优化之后状态定义和转移条件基本不变理解了基础版再看优化版会轻松很多。比赛时如果真的时间紧我有时候甚至会直接写记忆化搜索把状态看作 (j, l, i) 的三维选择虽然更慢但不容易写错。4. 常见错误与调试实录4.1 初始化与边界两个最容易WA的地方我在本地反复测试的时候第一个踩的坑是dp[0]的time值。一开始我把 dp[0].time 设成 -2T想着第一艘船 ready dp[0].time 2T 0和后面 j0 的情况统一处理代码写起来能少一个if。这个改法看着很对称一跑测试样例就发现不对当车辆到达时间很早时第一艘船可能在负时间就“ready”了实际却要等第一辆车到达才能发船导致 d 计算出问题。折腾半天最后还是老老实实加了个特判。第二个坑是超时条件的符号问题。判断空隙车是否已经离开时条件是 d a[l-1] W注意这里是严格大于不是大于等于。如果 d 恰好等于 a[l-1] W说明空隙里的最后一辆车在发船那一刻刚好到达等待上限它应该还在队列里、可以被装载而不是被拒。这种情况下跳过它是非法的。这个等号问题写的时候顺手一带很容易写错恰恰是WA的常见来源。边界条件还有一个容易漏掉的地方当前船段的第一辆车 l 和最后一辆车 i 之间如果 len 刚好等于 C没问题但如果 len 小于 C理论上船还有剩余容量为什么它不继续装 i 后面的车答案是因为 i 后面要么还没有车到达要么到达但已经超时要么原序列里i已经是最后一辆。这些情况在我们的枚举中都能被后续更大的i状态覆盖所以基础版代码里不需要额外判断“船是否真的装到i为止”。但如果你优化转移想直接从某个 i 跳到 next[i]就一定要考虑这个“船满没满”、“后面的车到没到”的问题否则优化版会漏状态。4.2 状态合并时的支配关系维护 dp[i] 的时候我一开始只保留了 cnt 最大的那个状态time 不管。结果样例都过自己构造的一组数据WA掉了。原因是在后续转移中time更小的状态可能让下一艘船更早出发最终多装几辆车。举一个简单的构造dp[i] 有两种方案方案A装了3辆车发船时间100方案B装了2辆车发船时间20。如果只看cnt方案A留在dp[i]里方案B被丢弃。但方案B因为船早回来可以在后续车流中再装2辆总共4辆方案A虽然眼前装得多但船晚回来后续一辆都装不上总共只有3辆。所以“cnt最大”和“time最小”存在矛盾时两个状态都不能随便丢。严格的处理应该是维护一个帕累托前沿把所有非支配状态都保留下来。不过竞赛里为了代码简单我一般默认采用“cnt优先time次优”的合并策略cnt更大的状态一定不劣于cnt更小的状态只有当cnt相同时才比较time。理由是在这道题里多装一辆车的收益几乎总是大于time提前带来的收益其实并不总是成立上面的反例就说明这个合并策略有漏洞。但在n比较小、数据不强的时候这种简化写法往往能AC所以我代码里仍用这个策略同时提醒自己不能盲目相信。如果你想要严谨可以把 dp[i] 改成 vector 存所有非支配状态转移时对每个状态分别扩展。代价是常数变大但正确性有保障。4.3 从暴力和优化看这类题的套路第一次AC之后我忍不住想这道题本质上就是在原序列上做分段每一段对应一艘船段与段之间允许存在“被时间淘汰”的空隙。整个转移过程和经典的“区间DP”很像但多了一个时间维度的联动。后来我把这种做法总结成了一套模板遇到类似的调度题就按这个顺序思考能不能把问题等价成“连续分段”问题。只要存在某种单调性比如等待超时按到达时间单调大概率可以。状态里必须携带足够的信息让下一段能独立计算。通常要记录“上一段的末尾位置”和“上一段结束后的某个关键时间”。转移的时候先枚举新段的起点和终点再找所有合法的上一段末尾。合法性的判断往往集中在几个边界条件上比如空隙超时、容量上限、等待上限。最后遍历所有可能的末尾位置取最优别默认最后一个元素必须被处理。这套模板写在笔记本上之后我后来又用它顺利解决了好几道类似的问题都是“若干个对象排队一个机器周期处理一批每个对象有等待上限”的模型。题目换皮不换里换的是发船周期变成生产节拍换的是渡轮变成大巴循环发车但DP骨架几乎一样。5. 这类“轮船问题”还能怎么考把这道题稍微变形能衍生出不少新题目。比如把“所有车都在同一岸等待”改成“两岸都有车船要双向装运”这时候状态就要再加入船所在的岸别转移的周期也不再是简单的2T。再比如把“每辆车最多等W分钟”改成“每辆车按照不同编号有不同的等待上限w[i]”条件是保留的但等待时间的单调性会被打破分段枚举就不能光看区间首尾了得改用前缀最值和双指针来维护。我实际遇到过一个变种船的容量不是固定C而是每辆车占用的长度不同相当于背包容量约束叠加在调度DP上。那才是真正的难度拉满单论“轮船问题”本身搞定分段和时间传递已经能解决这一大类题的80%框架。如果你是要刷透codevs 1620我的建议是先把基础版代码调通把所有输出中间状态的代码加上自己造几组小数据核对dp表。重点看两个地方一是每个dp[i]的time是否总是不小于上一段的发船时间二是空隙车的超时条件有没有被误判。这两点检查完基本就不会有太大问题。之后再尝试把三层循环优化掉一层你会发现优化反而逼迫你更深入理解状态之间的依赖关系很多之前没想明白的细节会在写优化的时候自己浮出来。