企业官网建设流程全解析

信息学奥赛一本通 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 次。这个思路在边际收益递减的情况下确实是对的，但题目数据完全不保证这个性质，所以贪心大概率会错。

构造一组能直接证伪的数据，N=3，M=3，盈利矩阵如下：

注意公司 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 台"这个决策下的总收益。

然后对所有合法的 k（0 到 j）取最大值，就是 dp[i][j] 的答案。

这里有个思维上的关键点：我们并不需要知道前面 i-1 个公司具体是怎么分的，只需要知道"它们在 j-k 台下的最好成绩是多少"。这就是最优子结构的体现——子问题的最优解可以直接拼装成大问题的最优解，而不需要保留子问题的具体方案。方案是在最后单独还原的，这个后面讲。

用生活化的类比：这就像公司发年终奖，先决定给部门 A 多少预算，剩下的钱交给部门 B 和 C 去分。你不需要知道 B 和 C 内部怎么分，只要知道"给定预算下它们能产出的最好业绩"就够了。

2.3 边界与初始化：分零台这件事必须显式处理

dp 数组的初始化有两处必须处理干净。

第一处是 j=0 那一列。任何数量的公司分 0 台设备，盈利必然是 0，所以 dp[i][0] = 0 对所有 i 成立。这个用全局数组默认值就能覆盖。

第二处是 i=0 那一行。0 个公司分 j 台设备，盈利也是 0，所以 dp[0][j] = 0 对所有 j 成立。同样，全局数组默认全 0，很多人不写这句也没事。但如果题目改成多组测试数据，或者 w 数组里出现负数，就必须显式初始化，否则会带着上一组数据的残留值继续算。

还有一处容易被忽略的是 w[i][0]。题目输入的矩阵只有 j 从 1 到 M 的列，w[i][0] 需要自己补上，值为 0。C++ 里全局数组默认就是 0，天然安全；Python 里如果你用列表推导初始化时只开到 m+1 列，索引 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 换一组方便手算的盈利矩阵

算法看一百遍不如自己填一遍表。为了把过程完整展示出来，这里换一组数据，N=3，M=3：

另外记住 w[i][0] = 0，也就是"分到 0 台时盈利为 0"，这一列在表里不显示，但计算时必须参与。

这张表适合手推的原因是：数值都不大，没有太多干扰，而且最终会出现两个并列最优的方案，正好用来说明"多解"这件事。

3.2 从 dp[1] 层推到 dp[3] 层

先算第 1 层，也就是只考虑公司 1。只有一个公司的时候，j 台设备全给它就是最优，所以 dp[1][j] 直接等于 w[1][j]：

dp[1][0] = 0，dp[1][1] = 3，dp[1][2] = 5，dp[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] = 0，dp[2][1] = max(dp[1][1]+0, dp[1][0]+2) = 3，dp[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 台。

把整张表整理出来：

答案就是右下角的 7。

3.3 从表格里读出最优值，也读出"多解"

注意 dp[2][3] 那一格，它是由两条不同的路径得到的，也就是说"公司 1 和公司 2 共分 3 台"这个子问题有两个最优解：公司 1 拿 2 台、公司 2 拿 1 台（5+2=7），或者公司 1 拿 1 台、公司 2 拿 2 台（3+4=7）。

因为公司 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]；这一格在枚举 k=1 时先被更新成 1，后来 k=2 时值相等没更新（因为用的是严格大于），所以 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[i+1][j-k] }，其中 0 ≤ k ≤ j。

边界是 suf[n+1][j] = 0。整张表从 i = n 往上推到 i = 1，suf[1][m] 就是全局最大盈利。

关键在后面的正向扫描：从 i = 1 开始，剩下的设备数是 rest，k 从 0 开始从小到大枚举，第一个满足 w[i][k] + suf[i+1][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 个公司的台数之后，问题缩小到 i+1 开始、rest-k 台的同类问题，重复同样的逻辑，第 i+1 个公司也会取到当前情况下的最少台数。逐位最小，合起来就是字典序最小。

用同一张表验证。先算后缀表：

suf[1][3] = 7，与之前的结果一致。然后正向扫描：

i=1，rest=3。k=0 时，0 + suf[2][3] = 6，不等于 7；k=1 时，3 + suf[2][2] = 3 + 4 = 7，命中。公司 1 分 1 台，rest 变成 2。

i=2，rest=2。k=0 时，0 + suf[3][2] = 2，不等于 4；k=1 时，2 + suf[3][1] = 3，不等于 4；k=2 时，4 + suf[3][0] = 4，命中。公司 2 分 2 台，rest 变成 0。

i=3，rest=0。k=0 时，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 作为答案。这个写法的思路是"让靠后的公司尽可能多拿，前面的自然就少拿"，听上去很像字典序最小，但严格来说它并不能保证。

构造一组极端数据来说明，N=3，M=2：

手算一遍，最优解有两个：(2,0,0) 和 (0,2,0)，收益都是 100。按字典序最小应该输出 (2,0,0)。

用倒推法走：从 dp[3][2] 开始，k 从 2 往小试。k=2 时，dp[2][0] + w[3][2] = 0 + 1 = 1，不等于 100；k=1 时，dp[2][1] + 1 = 11，也不等；k=0 时，dp[2][2] + 0 = 100，命中，公司 3 分 0 台。然后看 dp[2][2]，k 从 2 往小试，k=2 时 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[n+1]，所以数组第二维以上的行数要开到 n+2，这里直接开 25 是为了保险。越界是这类题最常见的运行时错误来源。

第二个是内层循环的初值。best 初始化为 0 是安全的，因为 k = 0 这一项 w[i][0] + suf[i+1][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，第 n+1 行的默认值就是 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]*(m+1)]*(n+2)，那所有行其实是同一个列表的引用，改一个地方会全变，这个坑非常隐蔽。

第三个差别是 suf 的行数。Python 里为了写 suf[i+1] 不越界，直接开 n+3 行，判断时不够的位置默认取 0，逻辑上正好等价于 suf[n+1][j] = 0。

如果换成 Java 写，思路一模一样，只是要注意数组要在方法里显式 new 出来，static 数组如果做多组数据需要每次清空；另外输出用 StringBuilder 拼接再一次性打印，比连续 System.out.println 快得多。

5.3 这份代码最容易踩的几类错误

把这道题常见的翻车点汇总成一张表，写完代码对着扫一遍：

其中"输入读反"这一条值得单独强调。一本通和洛谷的题面在措辞上略有不同，有些版本的题面把两个数字的先后顺序描述得比较模糊，读题时务必确认"第一个数是公司数还是设备数"。如果搞反了，在小数据上可能会算出看起来很合理但就是过不了的答案，很难从结果反推原因。

提示：调试期最简单的办法是在读入之后把 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 的方向写反之后，程序不会崩，只会算出一个看起来合理但偏小的答案，而且小数据还不一定能测出来。所以每次写完都拿题目样例对一遍，尤其是那些有多解的样例，看输出的是不是字典序最小那个，这一步能挡住大部分问题。