机器分配这四个字在动态规划题库里属于典型的看着平平无奇、上手就翻车。我第一次在信息学奥赛一本通 1266 里碰到它思路三分钟就有了代码十分钟敲完结果连着 WA 了五次——问题全卡在最后那个字典序最小上。后来到洛谷把 P2066 也刷了一遍才发现这俩其实是同一个模型套了两层皮核心都是把 M 台设备分给 N 个公司收益最大化,区别仅仅在输出格式。这道题的定位很清晰如果你刚学完分组背包或者资源分配类 DP它能一次性帮你把状态定义、决策枚举、方案还原三件事串起来如果你已经能独立 AC那它真正值得你回头琢磨的是为什么字典序最小这个约束会逼着我们把 DP 的方向反过来做。下面我按自己刷题、给别人讲题、帮人 debug 的完整流程把这道题从题面到代码全拆一遍。1. 题面重读把每个字的坑都挖出来1.1 输入输出到底长什么样先把题面原文摆出来这道题的表述非常教科书但恰恰是这种平淡的表述里藏着好几个坑。题目大意是总公司有高效设备 M 台准备分给下属的 N 个分公司各分公司拿到 j 台设备后能提供 a[i][j] 的盈利问怎么分配能让总盈利最大。数据范围很小M ≤ 15N ≤ 10。输入格式是这样的第一行两个整数 N 和 M接下来是一个 N 行 M 列的矩阵第 i 行第 j 个数表示第 i 个公司分到 j 台机器时的盈利。注意——这个矩阵是从 j1 开始的也就是说输入里没有给出 j0 的那一列分到 0 台机器的盈利默认是 0这一点必须自己在脑子里补上否则状态转移的时候很容易越界或者读到垃圾值。输出格式两版题不一样这是很多人第一次交题踩的坑版本第一行后续 N 行一本通 1266最大盈利值每行一个整数第 i 个分公司分到的机器数洛谷 P2066最大盈利值每行两个整数公司编号 分到的机器数DP 部分两题完全一样只是洛谷那版多输出了一列公司编号。我的建议是不管刷哪道都先花二十秒把输出格式对一遍因为这类题一旦格式错就是全 WA跟你算法对不对没关系特别打击心态。1.2 三个容易被忽略的约束第一总台数不超过 M。题面写的是总台数不超过设备总数 M而不是恰好等于 M。这个措辞上的差别在收益矩阵严格递增的常规数据里看不出来因为多给一台总能多赚一点必然用满 M 台但如果数据里有 a[i][j] a[i][j-1] 这种平台理论上就存在少发一台、收益不变、字典序更小的方案。我在实现时用的写法允许浪费机器配合这题的数据是安全的但心里要清楚这个边界。第二每家公司可以拿 0 台。每个公司有权获得任意数目的设备这个任意包含 0。状态转移里 k 必须从 0 开始枚举不能从 1 开始否则某些公司会被强制至少拿一台最优解直接错。第三同一个盈利值可能对应多组分配方案。这才是这道题的灵魂。题面明确要求输出字典序最小的那一个这六个字直接把题目难度从普及-抬到了普及/提高-的水准。1.3 一本通 1266 和洛谷 P2066 的差别除了输出格式字典序最小的具体定义两题是一致的把每个公司分到的机器数按公司编号 1 到 N 排成一个序列 (x1, x2, …, xn)在这个序列上比字典序。字典序的规则很朴素——先比 x1x1 小的更优x1 相等再比 x2以此类推。换句话说编号靠前的公司分到的机器数要尽可能少。我见过不少同学把字典序最小理解反了以为是前面的公司尽量多分结果样例都过不去——因为样例往往只有唯一解看不出对错。这里一定要把定义钉死序号小的位是高位高位越小越好。这个理解一旦偏了后面代码怎么写都是错的。2. 模型抽象它其实就是个分组背包2.1 把公司当成物品组很多人第一次看到分配两个字本能地想往贪心或者搜索上走——按性价比排序不行因为收益不是线性的第 i 个公司拿第 5 台机器的边际收益和第 1 台完全不同。穷举N 个公司、每个 0 到 M 台方案数是 C(NM, M) 这个量级N10、M15 的时候约 3268760其实勉强能搜但没有任何练习价值也不稳。正确的抽象是分组背包把这 N 个公司看成 N 个物品组第 i 组里有 M1 个候选物品分别代表第 i 个公司拿 0 台、1 台、…、M 台。背包容量就是 M 台机器每个物品的重量是它对应的机器数、价值是对应的盈利。因为每家公司的决策是互斥的只能选一个台数所以每组至多选一个这正是分组背包的标准结构。这个类比我每次讲题都会说你就想象 N 个抽屉每个抽屉里有 M1 张卡片每张卡片写着拿 j 台、赚多少钱你只能从每个抽屉里抽一张最后所有卡片上的台数加起来不超过 M求最大总金额。这么一想模型立刻就清晰了。2.2 状态定义为什么这么定最直觉的定义是dp[i][j]表示前 i 个公司一共分到 j 台机器的最大盈利也就是标准分组背包的写法。这个定义没错能算出正确答案但它在后面还原方案的时候会给你挖坑原因我放到第 3 章展开。另一条路是定义f[i][j]表示第 i 个到第 N 个公司一共分到 j 台机器的最大盈利是一种后缀式的状态。这两个定义在求最大值时是等价的都能得到同样的最优值但对字典序最小方案的还原友好度天差地别。经验告诉我凡是要在前/后方向上做贪心还原的题状态方向选对了就赢了一半。初始化的细节如果定义后缀状态那么f[N1][j] 0没有公司可分任何台数都赚 0这就是天然边界。如果定义前缀状态边界就是dp[0][j] 0。两种写法我下面都会给但主推后缀写法。2.3 复杂度与数据范围转移是三层循环枚举公司 i、枚举总台数 j、枚举给当前公司的台数 k所以时间复杂度是 O(N × M²)。代入最大值 N10、M15也就是 10 × 15 × 15 2250 次基本运算对任何评测机来说都是瞬间完成连常数都不用优化。空间上开一个f[20][20]的数组就够几十字节的事完全不需要滚动数组。我特别想强调的是这道题不要想复杂。有人看到字典序最小就想着先跑一遍 DP 求出最优值再 DFS 枚举所有最优方案挑最小的——理论上也能过因为数据范围小但代码量和出错概率翻好几倍纯属给自己找麻烦。老老实实做后缀 DP 加一次线性扫描的贪心还原二十行代码搞定。3. 字典序最小这道题真正的分水岭3.1 字典序到底比什么再强调一遍定义方案 A 的分配序列是 (a1, a2, …, an)方案 B 是 (b1, b2, …, bn)从 i1 开始逐个比较第一个不相等的位置谁小谁就赢。所以我们要做的事情是在所有达到最大盈利的方案里找到那个 x1 最小、在 x1 相同的前提下 x2 最小、依次类推的方案。这里有个非常自然的贪心想法既然要 x1 最小那就从公司 1 开始能少分就少分只要剩下的公司还能把剩余机器凑出最优值就行。这个贪心是正确的但前提是你能快速判断剩下那段能不能凑出最优——这个判断恰恰需要后缀 DP 的表。3.2 正向 DP 还原为什么一定会翻车这是我最想讲清楚的部分因为它解释了为什么那么多人DP 值算对了、方案还原出来却 WA。假设你用dp[i][j] 前 i 个公司分 j 台的最大盈利前缀定义最优值是dp[N][M]。还原的时候你只能从最后一个公司往回推枚举公司 N 拿了 k 台看dp[N-1][M-k] a[N][k]是否等于dp[N][M]。问题是当有多个 k 都满足时你选哪个选法直接影响最终输出的序列而无论你固定选最小还是最大都会在某些数据上挂掉。我准备了两组数据来证明这一点。第一组n2、m3两家公司的收益矩阵完全相同a[1] a[2] [0, 10, 20, 30]。任何满足 x1x23 的方案03、12、21、30都赚 30 分四个方案并列最优。字典序最小的是 (0,3)。用前缀 DP 还原、每一步选最小的 k在推公司 2 时 k0 满足dp[1][3]a[2][0]30于是 x20、x13输出 (3,0)这是字典序最大的那个直接错。第二组更狠n3、m4a[1] [0,10,10,10,10]a[2] [0,0,0,100,100]a[3] [0,50,85,140,140]。手推一下所有和为 4 的方案最大值 150达到 150 的只有 (0,3,1) 和 (1,0,3) 两个(0,3,1)010050(1,0,3)100140。字典序最小是 (0,3,1)。用前缀 DP 还原、每一步选最大的 k推公司 3 时看到 k3 满足先定 x33再往前推得 x20、x11输出 (1,0,3)又错。数据前缀 DP 每步选最小 k前缀 DP 每步选最大 k正确答案n2,m3,a 全为 [0,10,20,30](3,0) 错(0,3) 对(0,3)n3,m4,见上(0,3,1) 对(1,0,3) 错(0,3,1)看出来了吧两组的规律正好相反。根本原因是前缀 DP 是从后往前还原的而字典序要求从前往后优先。方向反了任何固定的 tie-break 规则都救不了。3.3 后缀 DP 从前往后贪心正确的做法是把状态定义反过来f[i][j]表示第 i 个到第 N 个公司一共分到 j 台机器能获得的最大盈利。转移方程是f[i][j] max{ a[i][k] f[i1][j-k] }k 从 0 枚举到 j边界f[N1][j] 0。这样算完之后f[1][M]就是全局最优值。还原的时候从公司 1 开始正着扫维护当前剩余机器数rem对每个公司 i从 k0 开始往上找第一个满足f[i][rem] a[i][k] f[i1][rem-k]的 k 就是这一位的最优选择。因为 k 是升序枚举的第一个命中的就是最小的合法 k恰好对应这一位取字典序最小而f[i1][rem-k]保证了后面必须还能凑出最优值。不断把 rem 减去 k扫到公司 N 就得到完整方案。为什么这个贪心一定对你可以这样理解f[i][rem]是从公司 i 开始的最优值我们挑满足等式的 k就是在不损失任何最优值的所有选择里挑最小的那个。由于字典序是从前往后比的每一步都取当前能取的最小值得到的序列就是全局字典序最小的这是贪心选择性质的标准体现。我拿上面第二组数据验算过后缀 DP 还原出来正是 (0,3,1)和手推一致。注意还原时的判断必须用精确相等不是也不是浮点近似。因为所有数都是整数DP 表里的值就是精确的最优值不存在精度问题。如果你写成或者会挑到非最优的 k方案就废了。4. 代码实现从读入到输出完整拆解4.1 变量与数组规划我习惯把数组开得比数据范围大一圈N 和 M 最大才 15我统一开 20省得算下标。核心就三个数组a[20][20]盈利矩阵。a[i][j]表示第 i 个公司拿 j 台的盈利a[i][0]恒为 0全局变量默认初始化就是 0正好省事但如果你把它开在局部要记得手动清零。f[20][20]后缀 DP 表。f[i][j]表示公司 i 到 N 共分 j 台的最大盈利。ans[20]存还原出来的每家公司的机器数。数组下标的对应关系一定要在纸上写清楚公司是第一个维度机器数是第二个维度。我见过有人把a[i][j]读成第 j 个公司第 i 台然后怎么调都不对最后发现是读入顺序写反了。4.2 后缀 DP 的三重循环关键是循环方向i 必须从 N 递减到 1因为f[i]依赖f[i1]。j 从 0 到 M 都可以但真正有用的只有f[1][M]这一条链上的值。k 从 0 到 j表示给公司 i 分配 k 台。for (int i n; i 1; i--) { for (int j 0; j m; j) { f[i][j] 0; // 先假设当前公司拿 0 台 for (int k 0; k j; k) { f[i][j] max(f[i][j], a[i][k] f[i1][j - k]); } } }一个小优化点k从j递减到 0 也能写但因为我们要的是最大值顺序无所谓。真正需要在意顺序的是还原那一步那里必须升序。关于f[N1][j]的取值还有个细节值得说。如果你写成全局数组f[N1][*]天然是 0代表剩下的机器不用也没关系符合总台数不超过 M的题面。如果你想强制恰好用完 M 台就把f[N1][0]设为 0、f[N1][j] -INFj0。这题数据下两种写法答案一样但如果收益矩阵里出现相等平台两者会给出不同的字典序方案选哪个取决于你对题面的理解。我个人倾向用 0和题面不超过的字面说法更贴合。4.3 方案还原的写法与坑点还原部分的代码只有几行但每一行都要小心int rem m; for (int i 1; i n; i) { for (int k 0; k rem; k) { // 升序第一个命中的就是最小解 if (f[i][rem] a[i][k] f[i1][rem - k]) { ans[i] k; rem - k; break; // 找到就跳出别继续找 } } }几个必须提醒的点第一rem - k千万别漏。它是保证前后一致性、也是保证最后每家公司的 k 加起来不超过 M 的关键。第二break一定要加。不加的话后面的 k 会覆盖前面的赋值你就选到了最大的 k正好和字典序最小的目标背道而驰——这就是 3.2 节第二组数据里选最大 k翻车的原因。第三内层循环上界是rem而不是m。因为剩余机器只有 rem 台给超过 rem 台是非法的a[i][k]越界无所谓数组够大读到 0但f[i1][rem-k]的下标会变成负数直接数组越界崩溃。第四理论上总能找到一个 k 让等式成立因为f[i][rem]本身就是这么算出来的所以不用加找不到的兜底分支但调试阶段可以在break前加个计数器看看每轮是否真的命中了。4.4 完整可 AC 代码含两版输出下面是我平时用的完整版本一本通那版把输出注释里的两条换一下即可#include bits/stdc.h using namespace std; int n, m; int a[20][20]; // a[i][j]: 第 i 个公司分到 j 台机器的盈利 int f[20][20]; // f[i][j]: 第 i..n 个公司共分 j 台机器的最大盈利 int ans[20]; // 还原出来的每个公司的分配数 int main() { cin n m; for (int i 1; i n; i) for (int j 1; j m; j) // 注意从 j1 读j0 天然是 0 cin a[i][j]; // 后缀 DPi 从大到小 for (int i n; i 1; i--) { for (int j 0; j m; j) { f[i][j] 0; for (int k 0; k j; k) { f[i][j] max(f[i][j], a[i][k] f[i 1][j - k]); } } } // 从前往后贪心还原取最小的合法 k int rem m; for (int i 1; i n; i) { for (int k 0; k rem; k) { if (f[i][rem] a[i][k] f[i 1][rem - k]) { ans[i] k; rem - k; break; } } } cout f[1][m] \n; // 洛谷 P2066 输出公司编号 机器数 for (int i 1; i n; i) cout i ans[i] \n; // 一本通 1266 只输出机器数换成下面这行即可 // for (int i 1; i n; i) cout ans[i] \n; return 0; }代码统共不到四十行核心部分就十几行。我建议第一次刷的时候不要抄自己照着 4.2、4.3 的思路敲一遍敲错了再回来对比直接抄效果好十倍。5. 手推验证与对拍5.1 样例推演全过程光看代码没感觉一定要手推一组数据把 DP 表填出来。用这组我自己造的三公司三设备样例3 3 30 40 50 20 30 50 20 25 30先算后缀 DP边界f[4][j] 0。公司 3 的表f[3][j] a[3][j]即 f[3][0..3] 0, 20, 25, 30。公司 2f[2][j] max_k (a[2][k] f[3][j-k])。f[2][1] max(020, 200) 20f[2][2] max(025, 2020, 300) 40f[2][3] max(030, 2025, 3020, 500) 50公司 1f[1][j] max_k (a[1][k] f[2][j-k])。f[1][3] max(050, 3040, 4020, 500) 70所以最大盈利是 70。开始还原rem 初始为 3公司 1k 从 0 试起k0 时 0f[2][3]05050≠70k1 时 30f[2][2]304070命中x11rem 变成 2。公司 2k0 时 0f[3][2]25≠40k1 时 20f[3][1]202040命中x21rem 变成 1。公司 3k0 时 0f[4][1]0≠20k1 时 20f[4][0]20命中x31rem 归 0。输出 70然后 1 1 / 2 1 / 3 1三家各一台正好三台分完。这组数据的最优解恰好唯一所以看不出字典序的作用验证字典序还得靠 5.2 那类数据。公司 if[i][0]f[i][1]f[i][2]f[i][3]3020253020204050103050705.2 自造数据验证字典序想验证字典序就用第 3 章那两组题。第一组2 3 10 20 30 10 20 30正确答案应该是 (0,3)最大盈利 30。跑一遍后缀 DPf[2][j]a[2][j]f[1][3]max(030, 1020, 2010, 300)30。还原时公司 1 的 k0 先命中 03030得 x10公司 2 剩 3 台从 k0 试0f[3][3]0≠30……一路试到 k3 命中 30得 x23、x3 没有。输出 (0,3)正确。注意第三家公司不存在我们只有 n2所以输出两行。第二组3 4 10 10 10 10 0 0 100 100 50 85 140 140正确答案 (0,3,1)最大盈利 150。这组我强烈建议你自己手推一遍后缀 DP重点看公司 2 那一层——a[2]前两个数是 0会制造大量并列正好用来考验还原时的升序枚举有没有写对。如果你跑出来是 (1,0,3)八成是还原时 k 没有升序、或者 break 写漏了。5.3 对拍脚本写完自己的版本最好再写个暴力对拍确认。暴力思路很简单DFS 枚举每个公司分多少台记录当前最优值和对应的分配序列当新方案的盈利等于当前最优、且序列字典序更小时更新答案。因为 N ≤ 10、M ≤ 15搜索空间在可接受范围内。然后写个随机数据生成器保证矩阵里是非递减的整数符合多给设备不多赚少的常见设定跑上一两千组就能把边界情况扫干净。对拍的时候重点盯两类数据一是矩阵里有大量相等数字的制造并列最优解二是 N 或 M 取极值 1 的考验边界。这两类最容易暴露字典序和下标越界的 bug。6. 常见错误速查与避坑心得6.1 速查表现象可能原因排查方向最大盈利值不对转移里 k 从 1 开始没让公司拿 0 台把 k 的初值改成 0盈利值对方案数字对不上还原时