在 codevs 上刷到 1620 这道“轮船问题”的时候我的第一反应是又一道 DP。真正动手写起来才发现这题拿部分分容易拿满分没那么轻松。关键不在状态定义多花哨而在于你愿不愿意把“装船”这个动作老老实实拆成若干个连续区间然后用递推把每种情况都算一遍。这篇文章我想把 codevs 1620 从模型抽象、状态设计、转移方程到三层优化、完整代码、踩坑实录一次性讲透。无论你是刚开始系统刷动态规划的 OI 选手还是准备蓝桥杯、洛谷 DP 专题的中学生这篇都可以直接当“轮船问题”的专题笔记来用。我会用一整套可复现的思路带你从读题走到 AC。1. 题目分析与模型抽象1.1 拿到题目先别急着写代码看懂“轮船问题”在说什么codevs 1620 这道题在题库里的编号很老但题干描述在网络上有好几个版本核心都一样有 n 件货物按顺序到达码头你要安排若干艘轮船把它们全部运走每艘船有载重限制也有对应的成本规则通常是固定出航费 按重量的运输费。问最小总花费是多少。这里有三件事容易读题时忽略第一货物顺序不能打乱。这不是普通的“往背包里塞东西”问题货物必须保持原有顺序船只能装走连续的若干件。这是整道题能不能用 DP 做的出发点。第二船可以不使用。不是 m 艘船必须全部出动如果有一艘船又贵又小那它就在状态里“闲置”着。第三每艘船最多使用一次。模型里每艘船只有出航和不出航两种选择。弄懂这三点其实题目就已经从“应用题”变成了“数学题”。接下来要做的是把文字描述翻译成可计算的形式。1.2 抽丝剥茧把装船过程抽象成线性划分模型我习惯在草稿纸上先画一条线把 n 件货物从左到右排开然后在缝隙上画切割线。每一段连续货物就是某艘船要运的货。比如 6 件货物分成 [1,2]、[3,4,5]、[6] 三段那就是三艘船各自负责一段段的顺序和货物顺序完全一致。对第 i 艘船来说假设它负责的是第 l 件到第 r 件货物那么它的成本可以写成cost base[i] unit[i] * sum(l, r)且 sum(l, r) limit[i]其中 base[i] 是固定出航费unit[i] 是单位重量运费limit[i] 是载重上限sum(l, r) 是区间货物总重量。如果区间重量超过载重这艘船就不能选这个区间。于是整个问题变成了把 [1, n] 这个区间划分成若干连续子区间分配给不超过 m 艘船每段区间的成本取决于分配给它的是哪艘船求最小总成本。这就是典型的“线性划分型 DP”——懂这个模型比背代码重要得多。1.3 跟经典动态规划题型的血缘关系第一次见这题的人可能会往背包问题方向想货物是物品船是背包但仔细一看货物有顺序限制不能任意组合所以它不是普通背包。它的结构更接近“任务调度”每艘船是一个处理阶段每件货物是一个必须按顺序完成的任务成本函数带区间性质。它和很多经典题都有血缘关系比如“石子合并”里的区间划分思想比如“乘积最大”里的“枚举最后一段”技巧再比如“乌龟棋”里的多阶段决策。它们的共同点是状态里都有一维表示“处理到第几个元素”转移时枚举最后一段的起点或长度。你一旦记住这个套路以后遇到“把序列分成若干段每段有代价求最小总代价”的题几乎都能用同一套思维框架去套。2. 动态规划状态设计与转移方程推导2.1 关键的思维第一步状态定义怎么来的线性划分型 DP 的状态设计有个固定的套路用一维表示“已经处理完多少件货物”用另一维表示“已经用到第几艘船”。我定义f[i][j] 表示前 i 艘船运走前 j 件货物所需的最小总花费。这个定义的好处是它完整覆盖了所有阶段信息船的数量用到了多少货物推进到了哪里。最终答案就是 f[m][n]即所有船都用完其实也用不完时运完所有货物的最小花费。可能你会问为什么不用 f[i][j] 表示“第 i 艘船运到第 j 件货物时的最小花费”也可以但那样状态含义更模糊转移时要考虑“第 i 艘船装了哪些货”这个集合容易把自己绕晕。而“前 i 艘船处理前 j 件”这个定义天然带有前缀视角转移起来特别清爽。2.2 转移方程从最后一段切入定义完状态最关键的一步是考虑“第 i 艘船最后做了什么”。第 i 艘船只有两种可能不参与运输那前 i-1 艘船就要搞定前 j 件货物即 f[i][j] f[i-1][j]。参与运输并且它装载的是最后 k 件货物也就是区间 [j-k1, j]。第二种情况下前 i-1 艘船负责前 j-k 件货物即 f[i-1][j-k]再加上第 i 艘船运第 [j-k1, j] 段的成本。所以转移方程是f[i][j] min(f[i-1][j], min over k ( f[i-1][j-k] base[i] unit[i] * sum(j-k1, j) ))其中 k 从 1 到 j但要满足区间重量 sum(j-k1, j) limit[i]。这个转移的核心思想叫“枚举最后一段”。它只关注最后一段从哪里开始前面部分完全交给子状态。这样做的好处是子问题和原问题结构完全一致只是规模和阶段数变小了天然满足 DP 的无后效性。2.3 边界条件与答案取值边界条件是 DP 最容易挂的地方。这道题有两个边界必须初始化f[0][0] 00 艘船运 0 件货成本当然是 0。 f[0][j] INFj 0没有船却要运货不可能给正无穷。 f[i][0] 0i 0无论有多少船不运货成本为 0。注意 f[i][0] 很容易被漏掉。如果你初始化时只写了 f[0][0] 0那么运行到 f[1][1] 时转移里会用到 f[0][0]这部分是对的但当 k j 时会用到 f[i-1][0]。如果 f[i-1][0] 是 INF那么“这一艘船运走全部货物”的情况就永远算不出来了答案会错得非常隐蔽。我早年刷题时就在这里栽过跟头后面会专门讲。INF 的取值也有讲究。如果用 int建议用 0x3f3f3f3f它大约是 10 亿量级足够大而且两个 INF 相加会溢出变成负数导致答案异常小这点在初始化时要用 memset 而不是手写循环或者直接用 long long 加 1LL 60。3. 复杂度分析与三层优化3.1 朴素转移的复杂度盲区先看朴素实现。状态数有 (m1) * (n1) 个每个状态转移时要枚举 k 从 1 到 j所以总复杂度是 O(m * n^2)。当 n 在 100 以内时这个复杂度毫无压力。但如果 m 和 n 都到 1000m * n^2 就是 10^9 级别在大多数 OJ 上会超时。所以刷这道题时你要先看清数据范围再决定要不要优化。我整理一下这个题常见的数据规模与可选算法数据规模时间复杂度说明n 100m 100O(m * n^2)朴素 DP 直接过n 1000m 1000O(m * n^2)需要用前缀和或提前 break 剪枝n 100000m 100成本统一O(m * n)需要前缀最小值优化这里要特别说明如果所有船的成本结构完全一样base 和 unit 都相同复杂度可以进一步降到 O(m * n)。但如果每艘船参数不同优化空间就会受限制这时 O(m * n^2) 往往就是能想到的最优方案——竞赛里出题人通常会把数据卡在恰好能过的范围。3.2 优化一前缀和与累计重量早停第一个优化其实非常朴素算区间和的时候不要每次都 for 循环累加。预处理一个前缀和数组 prefix[j] prefix[j-1] w[j]那么区间 [l, r] 的重量就是 prefix[r] - prefix[l-1]O(1) 时间拿到。更关键的是在转移枚举 k 的时候可以维护一个变量 sum 表示当前最后 k 件货物的总重量。因为货物重量一般是正整数k 越大最后一段区间越长重量越大。一旦 sum 超过当前船的 limit[i]更大的 k 必然也超限直接 break。这个剪枝在实际数据上效果很明显尤其当货物重量比较大、每艘船载重有限时内部循环往往跑不到 j 就提前退出了。实现上要注意sum 应该从 j 往前累加即从最后一件开始往前加因为 k 从小到大对应区间 [j-k1, j] 从右往左扩展。3.3 优化二滚动数组压掉船维二维 DP 在 n、m 都到 1000 时内存是 1000 * 1000 个 long long大约 8MB问题不大。但如果 n 到 10000二维就变 80MB部分 OJ 的内存限制是 64MB会 MLE。滚动数组的思路是观察转移方程f[i][j] 只依赖 f[i-1][...]上一艘船的状态跟更早的船没关系。所以不需要保留所有 i 的状态只需要两个一维数组g[j] 表示上一艘船处理完前 j 件的最小花费f[j] 表示当前船处理到前 j 件的最小花费。每一轮用 g 推出 f然后交换两个数组。这样内存从 O(m*n) 降到了 O(n)而且代码几乎不用大改。代价是你要理解“g 在转移中代表什么”写错就会变成经典的滚动数组事故本轮更新过的 f 被当作上一轮的值去用。3.4 优化三特殊条件下的前缀最小值优化如果所有船的 base 和 unit 完全相同比如 base Cunit U那么转移方程可以展开f[i][j] min over k ( f[i-1][j-k] C U * (prefix[j] - prefix[j-k]) ) C U * prefix[j] min over k ( f[i-1][j-k] - U * prefix[j-k] )令 t j-k则 t 从 0 到 j-1式子变成f[i][j] C U * prefix[j] min( f[i-1][t] - U * prefix[t] )t 属于 [0, j-1]你看括号里的值只跟 t 有关跟 j 无关。于是每处理一艘船时可以一边扫描 j 一边维护一个变量 best min(f[i-1][t] - U * prefix[t])每算完一个 f[i][j]就用它更新 best。这样整个转移变成 O(m * n)。但这里有个限制条件区间重量不能超过 limit。如果没有 limit这个优化是完美的有 limit 时合法的 t 有一个下界即 j 不能超过 t limit 内最多能装下的货物数量这就需要滑动窗口最小值来维护也就是单调队列。这一层进阶做法在本题里通常用不上不过能把思路理清楚对你理解“DP 优化怎么来的”非常有帮助。4. 完整代码实现与逐行解析4.1 二维 DP 参考实现好懂优先下面这份代码我故意写成最直观的二维版本先保证逻辑清晰适合初学者对着推导过程看。#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 1005; const int MAXM 1005; const ll INF 1LL 60; int n, m; ll w[MAXN]; // 每件货物重量 ll limit[MAXM]; // 每艘船载重上限 ll baseCost[MAXM]; // 每艘船固定出航成本 ll unitCost[MAXM]; // 每艘船单位重量运输成本 ll prefix[MAXN]; // 货物重量前缀和 ll f[MAXM][MAXN]; // f[i][j]前 i 艘船运走前 j 件货物的最小成本 ll rangeSum(int l, int r) { return prefix[r] - prefix[l - 1]; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; for (int i 1; i n; i) cin w[i]; for (int i 1; i m; i) { cin limit[i] baseCost[i] unitCost[i]; } for (int i 1; i n; i) prefix[i] prefix[i - 1] w[i]; for (int i 0; i m; i) for (int j 1; j n; j) f[i][j] INF; for (int i 0; i m; i) f[i][0] 0; for (int i 1; i m; i) { for (int j 1; j n; j) { f[i][j] f[i - 1][j]; // 第 i 艘船不参与运输 ll sum 0; for (int k 1; k j; k) { int l j - k 1; sum w[l]; if (sum limit[i]) break; ll cost baseCost[i] unitCost[i] * sum; f[i][j] min(f[i][j], f[i - 1][l - 1] cost); } } } cout f[m][n] \n; return 0; }这段代码有一个细节内部循环用 sum w[l] 的方式每增加一件货物就累计重量。因为 w 数组是正数所以一旦超重更大的 k 必然超重break 是安全的。这也是“提前退出”优化能成立的前提条件。4.2 滚动数组版本竞赛常用滚动数组版的核心是每一轮用“上一艘船的状态”算出“当前船的状态”然后交换。#include bits/stdc.h using namespace std; typedef long long ll; const int MAXN 1005; const int MAXM 1005; const ll INF 1LL 60; int n, m; ll w[MAXN], limit[MAXM], baseCost[MAXM], unitCost[MAXM]; ll prefix[MAXN]; ll g[MAXN], f[MAXN]; // g 是上一艘船的状态f 是当前船的状态 int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin n m; for (int i 1; i n; i) cin w[i]; for (int i 1; i m; i) { cin limit[i] baseCost[i] unitCost[i]; } for (int i 1; i n; i) prefix[i] prefix[i - 1] w[i]; for (int j 1; j n; j) g[j] INF; g[0] 0; for (int i 1; i m; i) { fill(f, f n 1, INF); f[0] 0; for (int j 1; j n; j) { f[j] g[j]; // 第 i 艘船不用 ll sum 0; for (int k 1; k j; k) { int l j - k 1; sum w[l]; if (sum limit[i]) break; ll cost baseCost[i] unitCost[i] * sum; f[j] min(f[j], g[l - 1] cost); } } memcpy(g, f, sizeof(f)); } cout g[n] \n; return 0; }注意滚动数组版本里f[j] 的初始化不能直接沿用二维版本的“先给所有 f 赋 INF再单独 f[0] 0”否则每轮之间旧数据会残留。所以我在每艘船开始前用 fill 清空再单独设置 f[0] 0。4.3 跟着样例手跑一遍 DP 表空讲方程容易飘我用手算一个简单例子带着你走一遍 DP 表。假设有 4 件货物重量分别是w [2, 3, 1, 4]有两艘船船 1limit 5base 2unit 1 船 2limit 8base 3unit 1先看 f[0][j]。没船可用时只有 f[0][0] 0其余全是 INF。f[1][1]船 1 运第 1 件重量 2成本 2 1 * 2 4。所以 f[1][1] 4。f[1][2]船 1 一次运走 2 件总重量 5成本 2 1 * 5 7。所以 f[1][2] 7。f[1][3]三件总重量 6超过船 1 载重 5所以一艘船运不走f[1][3] INF。这正好说明“状态为 INF 不只是初始化也可能是实际不可行”。f[1][4]四件总重 10超限同样 INF。到了第二艘船f[2][1]船 2 运第 1 件成本 3 1 * 2 5或者不用船 2沿用 f[1][1] 4。取小值 4。f[2][2]不用船 2 是 f[1][2] 7船 2 运两件总重 5成本 8船 2 只运第 2 件重量 3则 f[1][1] (3 3) 10。取小值 7。f[2][3]不用船 2 是 INF船 2 运全部三件总重 6成本 3 6 9f[1][0] 9 9船 2 运后两件总重 4f[1][1] (3 4) 11船 2 只运第 3 件f[1][2] (3 1) 11。取小值 9。f[2][4]船 2 运后两件 [1, 4]总重 5f[1][2] (3 5) 7 8 15船 2 运后三件 [3, 1, 4]总重 8f[1][1] (3 8) 4 11 15船 2 运全部四件总重 10超限不可行。所以 f[2][4] 15。把结果整理成表f[i][j]j0j1j2j3j4i00INFINFINFINFi1047INFINFi2047915最终答案 f[2][4] 15。这个手算结果可以用来验证代码输出。如果你写出来的程序在这个样例上得到 15那核心逻辑基本没跑偏。5. 常见问题与踩坑记录5.1 Bug 一INF 设置太小用 int 做 DP 时如果 INF 设成 1e9而累加过程中出现了两个 INF 相加结果可能不是一个大数而是溢出后的负数。负的 INF 会让 min 函数选出完全错误的值最后答案甚至可能是负数。我自己的习惯是要么用 long long 和 1LL 60要么用 int 和 0x3f3f3f3f。注意 0x3f3f3f3f 大约是 1.06e9两个相加约 2.1e9还没超过 int 上限所以 memset 配合 int 数组时可以放心用。但这题成本可能超过 1e9所以更推荐 long long。5.2 Bug 二漏掉 f[i][0] 0这个坑我在前面 2.3 节提过值得再强调一遍。很多初学者只初始化 f[0][0] 0其他全 INF结果转移时“一艘船运走前面所有货物”的情况全部变成 INF。表面上看代码没问题却总差那么几个点。如果用的是二维数组记得给每个 i 设置 f[i][0] 0。如果用的是一维滚动数组每轮开始前给当前数组的 f[0] 0。这是“空货物”这个合法状态的固定初始化。5.3 Bug 三货物顺序打乱导致全盘皆输我有次给朋友讲这题他反手就把货物按重量排了个序说是方便贪心。这题不能排序货物顺序是物理约束第 1 件货物必须在第 2 件之前装船你不可能让后面的货先走。排序以后DP 的“连续区间”性质就没了整个模型就崩了。做题时如果发现自己的“DP”莫名其妙地化成了贪心而且代码里还出现了 sort一定停下来想一想是不是把顺序约束给丢了。5.4 Bug 四超限 break 是否总是安全我在内部循环里用了“一旦累计重量超过 limit 就 break”这个写法成立的前提是货物重量为正。如果题目数据里出现重量为 0 或负数累计重量不再单调break 就会漏掉后面的合法状态。正常竞赛题不会给负重量但保险起见我建议在代码里直接枚举 k每次单独判断区间重量是否超限。虽然慢一点但更鲁棒。实际写题时你可以根据数据范围决定是否激进优化。5.5 几个值得记住的复盘经验这题做完之后我把它归到了自己 DP 模板库里的“序列划分型”分类。之后再遇到同类型的题识别速度明显快了很多。这里分享一张我自己整理的套路速查表题型特征状态设计思路转移技巧序列按顺序划分成若干段f[i][j] 表示前 i 段处理前 j 个元素枚举最后一段起点或长度有载重/容量限制把限制放进区间合法判断提前 break 或前缀和取区间和成本函数与区间有关预处理区间成本数组前缀和 公式展开降复杂度每艘船/每段可以选择不用增加“不选”这一分支f[i][j] f[i-1][j] 作为保底最后一列那条“不选分支”特别容易被忽略。很多 DP 题里每个物品“可选可不选”但这里每个阶段的“不选”意味着船或整体流程里的某个人力可以闲置这种状态如果漏掉你求出来的答案会偏大。我个人做这类题还有一个习惯不管题意多简单先手算一个 4 到 5 个数据的小样例把 DP 表完整列出来再对着代码跑一遍。手算的过程能暴露绝大多数方程写错、边界漏设的问题比直接交上去 WA 了再对拍效率高得多。这个习惯直到现在刷题我都在用尤其是遇到那种“看似一眼 DP实则细节拉满”的题手推表格永远是最快的调试方式。如果你正在刷 codevs 的题库或者在一本通、洛谷上做到同类型的“轮船问题”“装箱问题”建议你把文中的滚动数组版本自己敲一遍再用不同数据规模去试。代码是次要的能把“为什么这样转移”讲清楚这题才算真正过了。