信息学奥赛一本通 1266 这道【例9.10】机器分配几乎是我见过被方案输出卡住次数最多的一道动态规划入门题。值本身不难算一个二维 dp 加两层循环就出结果可真正让人在洛谷 P2066 上反复提交失败、看着满屏 WA 发呆的往往是怎么把最优解对应的分配方案还原出来这一小段。我第一次做的时候dp 部分五分钟写完输出方案那段改了四十多分钟中间还因为一个下标从 0 还是从 1 开始的问题多调了两轮。这篇东西就是把这四十多分钟里踩过的东西摊开来讲题目到底在约束什么、状态是怎么被想出来的、转移方程每一项在说什么、手推一张表长什么样、方案还原有几种写法、字典序最小到底怎么保证、代码落地的坑都在哪。不管你是刚学完背包问题想找一道题练手还是已经写完 dp 卡在输出上下面这些内容应该都能直接用。1. 从分设备到分层决策这道题到底在考什么1.1 三行题面里藏着三个容易读漏的约束题面本身很短总公司有 M 台相同设备分给 N 个分公司第 i 个公司分到 j 台能产生 w[i][j] 的盈利问怎么分让总盈利最大并输出方案。信息学奥赛一本通给的编号是 1266处在第九章动态规划的例题位置洛谷上的对应编号是 P2066。两边题面基本一致只是输入输出的排版细节稍有出入。看起来简单但有三处约束非常容易读漏而这三处恰好决定了代码怎么写。第一处是每个公司可以分到 0 台。题面里写的是每个公司有权获得任意数目的设备这个任意包含零。很多人写转移的时候下意识让 k 从 1 开始枚举结果在小数据上答案偏小还以为是转移方程写错了其实只是漏掉了一个合法决策。第二处是总台数不超过 M注意是不超过而不是恰好等于。这个差别在盈利矩阵全为非负时不影响结果因为多给设备不会让收益变少最优解一定用满。但如果数据里存在负盈利或者题目改成必须用完处理方式就不一样了这一点后面还会展开。第三处是输出格式。洛谷和一本通的题目都要求第一行输出最大盈利值后面 N 行每行两个整数分别是公司编号和该公司分到的设备数。编号从 1 开始不是从 0 开始这是纯格式分跟算法无关但每年都有人在这里掉分。提示不同 OJ 上同一道题的行末空格、换行数量要求可能不同。稳妥的做法是最后一行也输出换行符行内不要有多余空格。1.2 贪心为什么必然翻车一组三个公司的小数据就能证伪看到分配资源求最大收益很多人的第一反应是贪心每次把一台设备给当前边际收益最大的那个公司重复 M 次。这个思路在边际收益递减的情况下确实是对的但题目数据完全不保证这个性质所以贪心大概率会错。构造一组能直接证伪的数据N3M3盈利矩阵如下公司1 台2 台3 台113622223111注意公司 1 的边际收益是 1、2、3递增的。这种情况下贪心会怎么走第一步三家的第一台边际收益分别是 1、2、1贪心把设备给了公司 2累计收益 2状态变成 (0,1,0)。第二步公司 1 第一台还是 1公司 2 第二台只有 0公司 3 第一台是 1。最大值是 1公司 1 和公司 3 打平按编号小优先给公司 1累计收益 3状态变成 (1,1,0)。第三步公司 1 第二台的边际收益是 2公司 2 第二台是 0公司 3 第一台是 1。给公司 1累计收益 5最终方案 (2,1,0)总收益 5。而真正的最优解是 (3,0,0)收益 6。贪心少了 1。失败的根本原因在于贪心只看当前这一步的边际增量无法预判再坚持喂一个公司它下一台会突然给出更高回报。动态规划之所以必要就是因为它会把所有可能的分法都考虑一遍用状态把历史决策的影响记录下来。这也是为什么这道题被放在第九章例题的位置——它是一个把贪心不行、必须 DP讲得很干净的样本。1.3 它其实是一道分组背包状态为什么能直接照搬如果把视角换一下这道题其实就是分组背包。把每个公司看成一个组组内可选的项目是分 0 台、分 1 台、……、分 j 台选第 k 个项目就要消耗 k 的容量、换来 w[i][k] 的价值。总容量是 M每个组必须且只能选一个项目。这样就解释了两件事。一是为什么状态可以定义成前 i 个公司分 j 台因为这正是分组背包里前 i 组、容量 j的标准形式。二是为什么外层枚举公司、内层枚举容量、最内层枚举组内选择这个三层结构看起来眼熟——它就是分组背包的固定骨架。不过它比标准分组背包多了一层东西标准分组背包只要求输出最大价值而这道题要求把每一组到底选了哪个项目输出来。这个输出方案的需求才是它真正的难点也是把它的难度从模板题往上抬了一档的原因。2. dp[i][j] 是怎么被想出来的按公司分层的递推结构2.1 阶段、状态、决策三要素怎么对齐动态规划的思考起点永远是同一个问题这件事能不能切成若干个前后衔接的阶段在这道题里天然的切分方式是按公司一个一个处理。先只考虑第 1 个公司怎么分再考虑把第 1、2 个公司放在一起怎么分再到前 3 个……直到前 N 个。这就是阶段。状态要记录的信息只有两个处理到第几个公司了以及一共用掉了多少台设备。于是定义为 dp[i][j]把 j 台设备分配给前 i 个公司所能得到的最大盈利。这里 i 表示阶段j 表示资源消耗量两者合起来唯一确定一个子问题。决策就是第 i 个公司分几台。设它分到 k 台k 的取值范围是 0 到 j因为总共只有 j 台可以分。做出这个决策之后剩下的 j-k 台就全部交给前 i-1 个公司去处理这部分的最优值恰好就是 dp[i-1][j-k]。三个要素对齐之后转移方程几乎是自动浮现的不需要发明只需要翻译。2.2 转移方程的由来把最后一台设备的归属拆开写出转移方程dp[i][j] max{ dp[i-1][j-k] w[i][k] }其中 0 ≤ k ≤ j。这个式子看起来很朴素但每一项的含义值得逐字读一遍。dp[i-1][j-k] 是前面 i-1 个公司在拿到 j-k 台设备时能做出的最好成绩它已经把前面所有公司的分法都考虑完了是一个已经算好的、封装好的最优子结果。w[i][k] 是第 i 个公司拿到 k 台时的盈利。两项相加就是第 i 个公司拿 k 台这个决策下的总收益。然后对所有合法的 k0 到 j取最大值就是 dp[i][j] 的答案。这里有个思维上的关键点我们并不需要知道前面 i-1 个公司具体是怎么分的只需要知道它们在 j-k 台下的最好成绩是多少。这就是最优子结构的体现——子问题的最优解可以直接拼装成大问题的最优解而不需要保留子问题的具体方案。方案是在最后单独还原的这个后面讲。用生活化的类比这就像公司发年终奖先决定给部门 A 多少预算剩下的钱交给部门 B 和 C 去分。你不需要知道 B 和 C 内部怎么分只要知道给定预算下它们能产出的最好业绩就够了。2.3 边界与初始化分零台这件事必须显式处理dp 数组的初始化有两处必须处理干净。第一处是 j0 那一列。任何数量的公司分 0 台设备盈利必然是 0所以 dp[i][0] 0 对所有 i 成立。这个用全局数组默认值就能覆盖。第二处是 i0 那一行。0 个公司分 j 台设备盈利也是 0所以 dp[0][j] 0 对所有 j 成立。同样全局数组默认全 0很多人不写这句也没事。但如果题目改成多组测试数据或者 w 数组里出现负数就必须显式初始化否则会带着上一组数据的残留值继续算。还有一处容易被忽略的是 w[i][0]。题目输入的矩阵只有 j 从 1 到 M 的列w[i][0] 需要自己补上值为 0。C 里全局数组默认就是 0天然安全Python 里如果你用列表推导初始化时只开到 m1 列索引 0 的位置也默认是 0同样安全。但如果手动开辟数组并做初始化就需要显式处理。注意如果题目数据允许负盈利dp 数组要用极小值比如 -1e9初始化而不能用 0。否则那些其实拿不到任何正收益的状态会被错误地保留下来导致答案偏大。做题前扫一眼数据范围说明能省掉一次 WA。2.4 数据范围为什么给得这么小N 最多 10 个公司M 最多 15 台设备。这个范围非常小是出题人刻意给的因为三层循环的复杂度是 O(N × M × M)代进去就是 10 × 15 × 15 2250 次运算几乎瞬间出结果。这意味着两件事。一是这道题的设计重点根本不在算法效率上而在状态设计和方案还原的思路上它是一道思路题而非性能题。二是你完全不需要考虑滚动数组、前缀和优化之类的技巧老老实实用二维 dp 就够可读性比省内存重要得多。如果你在做题时看到这种小范围就大致可以判断这题的考点在建模和实现细节上不在优化上。相应地代码写得清晰可维护比写得紧凑更重要。3. 手推一张完整的 dp 表把七个格子填满3.1 换一组方便手算的盈利矩阵算法看一百遍不如自己填一遍表。为了把过程完整展示出来这里换一组数据N3M3公司1 台2 台3 台135622463123另外记住 w[i][0] 0也就是分到 0 台时盈利为 0这一列在表里不显示但计算时必须参与。这张表适合手推的原因是数值都不大没有太多干扰而且最终会出现两个并列最优的方案正好用来说明多解这件事。3.2 从 dp[1] 层推到 dp[3] 层先算第 1 层也就是只考虑公司 1。只有一个公司的时候j 台设备全给它就是最优所以 dp[1][j] 直接等于 w[1][j]dp[1][0] 0dp[1][1] 3dp[1][2] 5dp[1][3] 6。再算第 2 层dp[2][j] 表示把 j 台设备分给公司 1 和公司 2。以 dp[2][3] 为例公司 2 可以分 0、1、2、3 台公司 2 分 0 台dp[1][3] w[2][0] 6 0 6公司 2 分 1 台dp[1][2] w[2][1] 5 2 7公司 2 分 2 台dp[1][1] w[2][2] 3 4 7公司 2 分 3 台dp[1][0] w[2][3] 0 6 6最大值是 7而且有两条路径都能取到分别对应公司 2 分 1 台和公司 2 分 2 台。同理算出 dp[2][0] 0dp[2][1] max(dp[1][1]0, dp[1][0]2) 3dp[2][2] max(dp[1][2]0, dp[1][1]2, dp[1][0]4) 5。最后算第 3 层dp[3][3]公司 3 分 0 台dp[2][3] 0 7公司 3 分 1 台dp[2][2] 1 6公司 3 分 2 台dp[2][1] 2 5公司 3 分 3 台dp[2][0] 3 3最大值是 7对应公司 3 分 0 台。把整张表整理出来i \ j012300000103562035730357答案就是右下角的 7。3.3 从表格里读出最优值也读出多解注意 dp[2][3] 那一格它是由两条不同的路径得到的也就是说公司 1 和公司 2 共分 3 台这个子问题有两个最优解公司 1 拿 2 台、公司 2 拿 1 台527或者公司 1 拿 1 台、公司 2 拿 2 台347。因为公司 3 最终分的是 0 台这两个子问题的最优解都会传导到最终答案上所以全局也有两个最优方案方案 A公司 1 分 2 台公司 2 分 1 台公司 3 分 0 台总收益 7方案 B公司 1 分 1 台公司 2 分 2 台公司 3 分 0 台总收益 7如果你把方案按公司 1 的台数、公司 2 的台数、公司 3 的台数拼成一个序列方案 A 是 (2,1,0)方案 B 是 (1,2,0)。按字典序比较B 更小。这就是这道题真正麻烦的地方只要存在多解评测结果就取决于你输出的是哪一个。有的评测数据是 Special Judge任意最优解都算对有的则明确要求输出字典序最小的那个。为了不把命运交给评测机的宽容度按字典序最小来输出是最稳的选择。提示所谓按字典序最小比较的是 (公司 1 台数, 公司 2 台数, …, 公司 N 台数) 这个序列先比第一个分量相同再比第二个以此类推。所以核心目标只有一个——让编号小的公司分到的台数尽可能少。4. 方案还原三条路线以及字典序到底该怎么保4.1 路线一记录前驱的来源数组最直观的思路是在算 dp 的时候顺手记下每格是从哪个 k 转移来的。开一个 nxt[i][j] 数组当某次枚举的 k 让 dp[i][j] 变大的时候把 nxt[i][j] 更新成 k。算完之后从 nxt[n][m] 出发一路往前跳拿到第 n 个公司的台数把 j 减去它再看 nxt[n-1][j]依此类推。这个写法最大的优点是思路直白几乎就是把我刚刚是拿哪一步算出来的这句话翻译成了代码。缺点是回溯方向是反的——先确定的是最后一个公司第一个公司反而最后才确定这给字典序控制带来了麻烦后面会细说。用刚才那张表走一遍nxt[3][3] 记的是 0跳到 dp[2][3]这一格在枚举 k1 时先被更新成 1后来 k2 时值相等没更新因为用的是严格大于所以 nxt[2][3] 1再跳到 dp[1][2]nxt[1][2] 2。还原出方案 (2,1,0)是方案 A并不是字典序最小的那个。4.2 路线二后缀 DP 加正向贪心真正能在数学上保证字典序最小的做法是反向定义状态、正向构造方案。先定义 suf[i][j]把 j 台设备分给第 i 个到第 n 个公司所能得到的最大盈利。转移方程形式和之前一样只是方向反了suf[i][j] max{ w[i][k] suf[i1][j-k] }其中 0 ≤ k ≤ j。边界是 suf[n1][j] 0。整张表从 i n 往上推到 i 1suf[1][m] 就是全局最大盈利。关键在后面的正向扫描从 i 1 开始剩下的设备数是 restk 从 0 开始从小到大枚举第一个满足 w[i][k] suf[i1][rest-k] suf[i][rest] 的 k 就是第 i 个公司应该分到的台数。为什么这样就能保证字典序最小因为 suf[i][rest] 的定义本身就保证了剩下的 rest 台分给 i 到 n 这些公司能达到的理论最优值是 suf[i][rest]。当我们找到第一个满足等式的 k 时说明让第 i 个公司只拿 k 台、把 rest-k 台留给后面依然能取到全局最优。既然 k 是从小到大找的第一个找到的 k 就是第 i 个公司可能分到的最少台数。固定了第 i 个公司的台数之后问题缩小到 i1 开始、rest-k 台的同类问题重复同样的逻辑第 i1 个公司也会取到当前情况下的最少台数。逐位最小合起来就是字典序最小。用同一张表验证。先算后缀表i \ j012340000301232024610357suf[1][3] 7与之前的结果一致。然后正向扫描i1rest3。k0 时0 suf[2][3] 6不等于 7k1 时3 suf[2][2] 3 4 7命中。公司 1 分 1 台rest 变成 2。i2rest2。k0 时0 suf[3][2] 2不等于 4k1 时2 suf[3][1] 3不等于 4k2 时4 suf[3][0] 4命中。公司 2 分 2 台rest 变成 0。i3rest0。k0 时0 suf[4][0] 0等于 suf[3][0] 0命中。公司 3 分 0 台。方案 (1,2,0)正是方案 B字典序最小。4.3 路线三直接从 dp[n][m] 倒推以及它为什么会翻车网上流传最广的一种写法是用普通的 dp[i][j]回溯的时候对第 i 个公司从 j 往小枚举 k找到第一个满足 dp[i][j] dp[i-1][j-k] w[i][k] 的 k 作为答案。这个写法的思路是让靠后的公司尽可能多拿前面的自然就少拿听上去很像字典序最小但严格来说它并不能保证。构造一组极端数据来说明N3M2公司1 台2 台110100210100311手算一遍最优解有两个(2,0,0) 和 (0,2,0)收益都是 100。按字典序最小应该输出 (2,0,0)。用倒推法走从 dp[3][2] 开始k 从 2 往小试。k2 时dp[2][0] w[3][2] 0 1 1不等于 100k1 时dp[2][1] 1 11也不等k0 时dp[2][2] 0 100命中公司 3 分 0 台。然后看 dp[2][2]k 从 2 往小试k2 时 dp[1][0] 100 100命中公司 2 分 2 台。最后 dp[1][0]公司 1 分 0 台。输出 (0,2,0)。字典序比正确答案大倒推法在这里翻了车。翻车的根源在于倒推法在每一步都优先让当前这个靠后的公司多拿但靠后的公司多拿和编号最小的公司少拿之间没有必然的等价关系。数据稍微极端一点这个隐式假设就崩了。我的建议很直接如果你在意字典序就用「后缀 DP 正向贪心」这条路它在逻辑上是可证明的不依赖数据是否友好。如果你只是想快速过题用来源数组记录前驱也完全可以但要有心理准备某些数据下可能会被判错。注意还有一种做法是在倒推时把 k 从小到大枚举这在很多情况下能凑出字典序最小的结果但它同样不是严格证明的遇到第一个公司之外的位次仍然可能出错。想省心就用后缀 DP 那条路。5. 代码落地C 与 Python 两套实现附自查清单5.1 C 后缀 DP 完整实现#include bits/stdc.h using namespace std; int n, m; int w[20][20]; // w[i][j]: 第 i 个公司分 j 台的盈利w[i][0] 0 int suf[25][20]; // suf[i][j]: 第 i..n 个公司分 j 台的最大盈利 int main() { cin n m; for (int i 1; i n; i) for (int j 1; j m; j) cin w[i][j]; // 后缀 DP从最后一个公司往前推 for (int i n; i 1; --i) { for (int j 0; j m; j) { int best 0; for (int k 0; k j; k) { int cur w[i][k] suf[i 1][j - k]; if (cur best) best cur; } suf[i][j] best; } } cout suf[1][m] \n; // 正向贪心还原方案k 从小到大找第一个可行的 int rest m; for (int i 1; i n; i) { for (int k 0; k rest; k) { if (w[i][k] suf[i 1][rest - k] suf[i][rest]) { cout i k \n; rest - k; break; } } } return 0; }代码里有三个细节值得单独说。第一个是 suf 数组的大小。suf[i] 在 i n 时会用到 suf[n1]所以数组第二维以上的行数要开到 n2这里直接开 25 是为了保险。越界是这类题最常见的运行时错误来源。第二个是内层循环的初值。best 初始化为 0 是安全的因为 k 0 这一项 w[i][0] suf[i1][j] 一定是个非负值盈利按题目约定为正整数或非负循环一定会更新至少一次。但如果数据里可能有负数就要初始化成一个足够小的值。第三个是还原方案时不必担心死循环。因为每一层至少有一个 k 能满足等式——suf[i][rest] 的定义就保证了这样的 k 一定存在。如果循环跑完都没 break那说明前面的表算错了。5.2 Python 实现与输入处理上的差别import sys def main(): data sys.stdin.read().split() if not data: return idx 0 n int(data[idx]); idx 1 m int(data[idx]); idx 1 w [[0] * (m 1) for _ in range(n 2)] for i in range(1, n 1): for j in range(1, m 1): w[i][j] int(data[idx]); idx 1 # 后缀 DP第 n1 行的默认值就是 0 suf [[0] * (m 1) for _ in range(n 3)] for i in range(n, 0, -1): for j in range(m 1): best 0 for k in range(j 1): cur w[i][k] suf[i 1][j - k] if cur best: best cur suf[i][j] best print(suf[1][m]) rest m for i in range(1, n 1): for k in range(rest 1): if w[i][k] suf[i 1][rest - k] suf[i][rest]: print(i, k) rest - k break main()Python 这套代码在逻辑上和 C 完全一样差别主要在输入处理上。第一个差别是读入方式。用 sys.stdin.read().split() 一次性把所有 token 读到列表里再用指针顺序取比逐行 input() 稳得多也不用担心行尾空格、空行、多余换行这些格式问题。数据量小时看着有点重但这是最不容易出错的写法。第二个差别是数组的初始化。Python 里列表推导式生成的二维数组每一个内层列表都是独立对象不会出现改一行结果所有行都变了的坑。如果你图省事写成[[0]*(m1)]*(n2)那所有行其实是同一个列表的引用改一个地方会全变这个坑非常隐蔽。第三个差别是 suf 的行数。Python 里为了写 suf[i1] 不越界直接开 n3 行判断时不够的位置默认取 0逻辑上正好等价于 suf[n1][j] 0。如果换成 Java 写思路一模一样只是要注意数组要在方法里显式 new 出来static 数组如果做多组数据需要每次清空另外输出用 StringBuilder 拼接再一次性打印比连续 System.out.println 快得多。5.3 这份代码最容易踩的几类错误把这道题常见的翻车点汇总成一张表写完代码对着扫一遍症状可能原因排查方法答案偏小漏掉了 k 0 的情况或 w[i][0] 没有置 0检查内层循环起点是否为 0答案偏大dp 数组没有正确初始化残留了上一次的值多组数据时显式清零输出格式错公司编号从 0 开始或行内用了多余空格对照题面样例逐字符比对多解被判错输出的是字典序较大的方案改用后缀 DP 加正向贪心数组越界崩溃suf 只开到 n1 行访问了 n2 行把行数开大一点不要抠输入读反把设备总数当成了公司数先看题目哪一个是公司哪一个是设备输入顺序搞混矩阵是 N 行 M 列写成了 M 行 N 列打印读进来的数据核对一遍其中输入读反这一条值得单独强调。一本通和洛谷的题面在措辞上略有不同有些版本的题面把两个数字的先后顺序描述得比较模糊读题时务必确认第一个数是公司数还是设备数。如果搞反了在小数据上可能会算出看起来很合理但就是过不了的答案很难从结果反推原因。提示调试期最简单的办法是在读入之后把 n、m 和整个矩阵打印一遍跟题目样例对比。这一步花十秒能省掉半小时的盲调。6. 把机器分配的骨架搬到别的题上6.1 资源分配型 DP 的通用骨架这道题真正值钱的地方是它给出了一套可以反复复用的骨架把有限的资源分给若干个接收方每个接收方在不同资源量下产出不同的收益求总收益最大。骨架长这样。第一确定阶段通常是接收方的编号。第二确定状态通常是前 i 个接收方用了 j 份资源。第三确定决策通常是第 i 个接收方拿 k 份k 从 0 到 j。第四写出转移 dp[i][j] max(dp[i-1][j-k] gain[i][k])。第五如果需要方案按后缀 DP 加正向贪心的方式还原。这套骨架的适应面非常宽。投资分配、任务调度、带宽划分、时间片分配、奖金包拆分只要符合资源可分、收益可枚举、各部分独立累加这三个条件就能直接套。6.2 几道可以直接套用的练习想把这套骨架练熟可以按下面的顺序刷。第一层是纯分组背包比如洛谷上的分组背包模板题只需要求最大值不涉及方案输出用来把三层循环的写法和边界处理打牢。第二层是带方案输出的资源分配题也就是这道机器分配本身重点体会后缀 DP 和正向贪心的配合。第三层是有额外约束的变体比如要求每个接收方至少分到一定数量、或者资源必须全部分完、或者收益函数是分段给出的。这类题只需要在转移的枚举范围上做限制骨架完全不变。刷的时候不要贪多同一类题连续做三道比三道不同类型的题各做一遍效果好得多。因为套路的价值在于形成肌肉记忆而肌肉记忆靠的是重复不是新鲜感。6.3 三种常见变体的改造思路第一种变体是每家公司至少分 1 台。改动很小只需要把内层枚举的起点从 0 改成 1同时把无解的状态标记出来。不过要注意如果 N 大于 M那就不存在合法方案需要提前判断。第二种变体是最优方案必须输出全部。也就是把所有能达到最大收益的方案都打印出来。这个要用搜索回溯从 suf 表出发在每一层找出所有满足等式的 k分支递归下去。由于数据规模小搜索完全不会超时。第三种变体是设备必须用完且盈利可能为负。这时要注意两点转移的枚举范围不变但 dp 的初值要用极小值另外最后的答案不再是 dp[n][m] 而是 dp[n][m]因为必须用满不需要在 dp[n][0..m] 里取最大值。如果题目改成不超过 M 台并且有负盈利答案就要在 dp[n][0..m] 里取最大值。我在实际写这类题的时候习惯先把转移方程和边界在纸上写一遍再动手敲代码。这道题的转移式子只有一行但边界条件和还原逻辑占了总代码量的一半以上纸上先理清楚能省掉大量调试时间。另外一个我自己踩过的坑是后缀 DP 的方向写反之后程序不会崩只会算出一个看起来合理但偏小的答案而且小数据还不一定能测出来。所以每次写完都拿题目样例对一遍尤其是那些有多解的样例看输出的是不是字典序最小那个这一步能挡住大部分问题。