企业官网建设流程全解析

"机器分配"这四个字，在动态规划题库里属于典型的"看着平平无奇、上手就翻车"。我第一次在信息学奥赛一本通 1266 里碰到它，思路三分钟就有了，代码十分钟敲完，结果连着 WA 了五次——问题全卡在最后那个"字典序最小"上。后来到洛谷把 P2066 也刷了一遍，才发现这俩其实是同一个模型套了两层皮：核心都是"把 M 台设备分给 N 个公司，收益最大化",区别仅仅在输出格式。这道题的定位很清晰：如果你刚学完分组背包或者资源分配类 DP，它能一次性帮你把"状态定义、决策枚举、方案还原"三件事串起来；如果你已经能独立 AC，那它真正值得你回头琢磨的，是为什么"字典序最小"这个约束会逼着我们把 DP 的方向反过来做。下面我按自己刷题、给别人讲题、帮人 debug 的完整流程，把这道题从题面到代码全拆一遍。

1. 题面重读：把每个字的坑都挖出来

1.1 输入输出到底长什么样

先把题面原文摆出来，这道题的表述非常"教科书"，但恰恰是这种平淡的表述里藏着好几个坑。题目大意是：总公司有高效设备 M 台，准备分给下属的 N 个分公司，各分公司拿到 j 台设备后能提供 a[i][j] 的盈利，问怎么分配能让总盈利最大。数据范围很小：M ≤ 15，N ≤ 10。

输入格式是这样的：第一行两个整数 N 和 M；接下来是一个 N 行 M 列的矩阵，第 i 行第 j 个数表示第 i 个公司分到 j 台机器时的盈利。注意——这个矩阵是从 j=1 开始的，也就是说输入里没有给出 j=0 的那一列，分到 0 台机器的盈利默认是 0，这一点必须自己在脑子里补上，否则状态转移的时候很容易越界或者读到垃圾值。

输出格式两版题不一样，这是很多人第一次交题踩的坑：

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)，在这个序列上比字典序。字典序的规则很朴素——先比 x1，x1 小的更优；x1 相等再比 x2，以此类推。换句话说，编号靠前的公司分到的机器数要尽可能少。

我见过不少同学把"字典序最小"理解反了，以为是"前面的公司尽量多分"，结果样例都过不去——因为样例往往只有唯一解，看不出对错。这里一定要把定义钉死：序号小的位是高位，高位越小越好。这个理解一旦偏了，后面代码怎么写都是错的。

2. 模型抽象：它其实就是个分组背包

2.1 把"公司"当成"物品组"

很多人第一次看到"分配"两个字，本能地想往贪心或者搜索上走——按性价比排序？不行，因为收益不是线性的，第 i 个公司拿第 5 台机器的边际收益和第 1 台完全不同。穷举？N 个公司、每个 0 到 M 台，方案数是 C(N+M, M) 这个量级，N=10、M=15 的时候约 3268760，其实勉强能搜，但没有任何练习价值，也不稳。

正确的抽象是分组背包：把这 N 个公司看成 N 个"物品组"，第 i 组里有 M+1 个候选物品，分别代表"第 i 个公司拿 0 台、1 台、…、M 台"。背包容量就是 M 台机器，每个物品的重量是它对应的机器数、价值是对应的盈利。因为每家公司的决策是互斥的（只能选一个台数），所以每组至多选一个，这正是分组背包的标准结构。

这个类比我每次讲题都会说：你就想象 N 个抽屉，每个抽屉里有 M+1 张卡片，每张卡片写着"拿 j 台、赚多少钱"，你只能从每个抽屉里抽一张，最后所有卡片上的台数加起来不超过 M，求最大总金额。这么一想，模型立刻就清晰了。

2.2 状态定义为什么这么定

最直觉的定义是dp[i][j]表示"前 i 个公司一共分到 j 台机器的最大盈利"，也就是标准分组背包的写法。这个定义没错，能算出正确答案，但它在后面"还原方案"的时候会给你挖坑，原因我放到第 3 章展开。

另一条路是定义f[i][j]表示"第 i 个到第 N 个公司一共分到 j 台机器的最大盈利"，是一种后缀式的状态。这两个定义在求最大值时是等价的，都能得到同样的最优值，但对"字典序最小方案"的还原友好度天差地别。经验告诉我，凡是要在"前/后"方向上做贪心还原的题，状态方向选对了就赢了一半。

初始化的细节：如果定义后缀状态，那么f[N+1][j] = 0（没有公司可分，任何台数都赚 0），这就是天然边界。如果定义前缀状态，边界就是dp[0][j] = 0。两种写法我下面都会给，但主推后缀写法。

2.3 复杂度与数据范围

转移是三层循环：枚举公司 i、枚举总台数 j、枚举给当前公司的台数 k，所以时间复杂度是 O(N × M²)。代入最大值 N=10、M=15，也就是 10 × 15 × 15 = 2250 次基本运算，对任何评测机来说都是瞬间完成，连常数都不用优化。空间上开一个f[20][20]的数组就够，几十字节的事，完全不需要滚动数组。

我特别想强调的是：这道题不要想复杂。有人看到"字典序最小"就想着先跑一遍 DP 求出最优值，再 DFS 枚举所有最优方案挑最小的——理论上也能过，因为数据范围小，但代码量和出错概率翻好几倍，纯属给自己找麻烦。老老实实做后缀 DP 加一次线性扫描的贪心还原，二十行代码搞定。

3. 字典序最小：这道题真正的分水岭

3.1 字典序到底比什么

再强调一遍定义：方案 A 的分配序列是 (a1, a2, …, an)，方案 B 是 (b1, b2, …, bn)，从 i=1 开始逐个比较，第一个不相等的位置谁小谁就赢。所以我们要做的事情是：在所有达到最大盈利的方案里，找到那个 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 都满足时，你选哪个？选法直接影响最终输出的序列，而无论你固定选最小还是最大，都会在某些数据上挂掉。我准备了两组数据来证明这一点。

第一组，n=2、m=3，两家公司的收益矩阵完全相同：a[1] = a[2] = [0, 10, 20, 30]。任何满足 x1+x2=3 的方案（0+3、1+2、2+1、3+0）都赚 30 分，四个方案并列最优。字典序最小的是 (0,3)。用前缀 DP 还原、每一步选最小的 k：在推公司 2 时 k=0 满足dp[1][3]+a[2][0]=30，于是 x2=0、x1=3，输出 (3,0)，这是字典序最大的那个，直接错。

第二组更狠，n=3、m=4：a[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)=0+100+50，(1,0,3)=10+0+140）。字典序最小是 (0,3,1)。用前缀 DP 还原、每一步选最大的 k：推公司 3 时看到 k=3 满足，先定 x3=3，再往前推得 x2=0、x1=1，输出 (1,0,3)，又错。

看出来了吧，两组的规律正好相反。根本原因是：前缀 DP 是从后往前还原的，而字典序要求从前往后优先。方向反了，任何固定的 tie-break 规则都救不了。

3.3 后缀 DP + 从前往后贪心

正确的做法是把状态定义反过来：f[i][j]表示"第 i 个到第 N 个公司一共分到 j 台机器能获得的最大盈利"。转移方程是

f[i][j] = max{ a[i][k] + f[i+1][j-k] }，k 从 0 枚举到 j

边界f[N+1][j] = 0。这样算完之后，f[1][M]就是全局最优值。

还原的时候从公司 1 开始，正着扫：维护当前剩余机器数rem，对每个公司 i，从 k=0 开始往上找，第一个满足f[i][rem] == a[i][k] + f[i+1][rem-k]的 k 就是这一位的最优选择。因为 k 是升序枚举的，第一个命中的就是最小的合法 k，恰好对应"这一位取字典序最小"，而f[i+1][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[i+1]。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[i+1][j - k]); } } }

一个小优化点：k从j递减到 0 也能写，但因为我们要的是最大值，顺序无所谓。真正需要在意顺序的是还原那一步，那里必须升序。

关于f[N+1][j]的取值，还有个细节值得说。如果你写成全局数组，f[N+1][*]天然是 0，代表"剩下的机器不用也没关系"，符合"总台数不超过 M"的题面。如果你想强制"恰好用完 M 台"，就把f[N+1][0]设为 0、f[N+1][j] = -INF（j>0）。这题数据下两种写法答案一样，但如果收益矩阵里出现相等平台，两者会给出不同的字典序方案，选哪个取决于你对题面的理解。我个人倾向用 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[i+1][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[i+1][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++) // 注意从 j=1 读，j=0 天然是 0 cin >> a[i][j]; // 后缀 DP：i 从大到小 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。

公司 2：f[2][j] = max_k (a[2][k] + f[3][j-k])。

• f[2][1] = max(0+20, 20+0) = 20
• f[2][2] = max(0+25, 20+20, 30+0) = 40
• f[2][3] = max(0+30, 20+25, 30+20, 50+0) = 50

公司 1：f[1][j] = max_k (a[1][k] + f[2][j-k])。

• f[1][3] = max(0+50, 30+40, 40+20, 50+0) = 70

所以最大盈利是 70。开始还原，rem 初始为 3：

公司 1，k 从 0 试起：k=0 时 0+f[2][3]=0+50=50≠70；k=1 时 30+f[2][2]=30+40=70，命中，x1=1，rem 变成 2。

公司 2，k=0 时 0+f[3][2]=25≠40；k=1 时 20+f[3][1]=20+20=40，命中，x2=1，rem 变成 1。

公司 3，k=0 时 0+f[4][1]=0≠20；k=1 时 20+f[4][0]=20，命中，x3=1，rem 归 0。

输出 70，然后 1 1 / 2 1 / 3 1，三家各一台，正好三台分完。这组数据的最优解恰好唯一，所以看不出字典序的作用，验证字典序还得靠 5.2 那类数据。

5.2 自造数据验证字典序

想验证字典序，就用第 3 章那两组题。第一组：

2 3 10 20 30 10 20 30

正确答案应该是 (0,3)，最大盈利 30。跑一遍后缀 DP：f[2][j]=a[2][j]，f[1][3]=max(0+30, 10+20, 20+10, 30+0)=30。还原时公司 1 的 k=0 先命中 0+30=30，得 x1=0；公司 2 剩 3 台，从 k=0 试，0+f[3][3]=0≠30……一路试到 k=3 命中 30，得 x2=3、x3 没有。输出 (0,3)，正确。注意第三家公司不存在，我们只有 n=2，所以输出两行。

第二组：

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 速查表