写动态规划时，最容易卡住的地方往往不是循环，而是这句话：dp[i] 究竟表示什么？如果状态只写成“到 i 的最优解”，那么“恰好到达”和“不超过 i”就可能混在一起，初始化也会跟着出错。

本文用两道题练习两个不同的状态轴：一题按已使用的长度递推，另一题按数值大小递推。建议先独立画出状态表，再看代码。

1. 两道题，两个关键问题

题目 官方难度 官方标签 本文训练重点
189A · Cut Ribbon 1300 brute force、dp 恰好填满与不可达状态
455A · Boredom 1500 dp 按值聚合与相邻冲突

名称、难度和标签于 2026-09-05 通过 Codeforces 官方 API 核对。下文是原创建模与解法说明，不是题面翻译；所有推演表均使用自拟例子。

读过 贪心三题 后，可以把这篇当作下一步：当一个局部选择无法保证未来仍然最优时，保留不同状态的最优结果，之后再比较。

2. Cut Ribbon：为什么不能一直选最短的一段

给定总长度 n，每段只能取 a、b、c 三种正整数长度，目标是在不剩余材料的前提下，让段数最多。题目保证有解，四个输入数均不超过 4000。

先看反例：总长度为 7，允许长度为 2、3、5。连续取最短的 2，会留下无法处理的 1；合法最优方案却是 2 + 2 + 3，共 3 段。

“短段更有利”只是方向感。能否恰好填满剩余长度，必须进入状态。

定义状态与初始化

定义 dp[len] 为：恰好拼出长度 len 时，最多可以使用多少段。

  • dp[0] = 0：空方案恰好拼出 0，使用 0 段。
  • 其余位置初始化为 -1：暂时没有合法方案。
  • 因为合法段数必定非负，这里的 -1 可以明确代表不可达。

不能把整个数组初始化为 0。例如允许长度 2、3、5 时，长度 1 不可达，不能在这个“假方案”后再接一段。

从最后一段反推转移

假设最后一段长度为 piece，去掉它后，前面的段必须恰好拼出 len - piece。只有前驱可达时，才考虑候选值 dp[len - piece] + 1。

仍用 n=7，长度集合={2,3,5} 手算：

len 0 1 2 3 4 5 6 7
dp[len] 0 不可达 1 1 2 2 3 3
一种最优拆法 空 — 2 3 2+2 2+3 2+2+2 2+2+3

注意长度 5 可以直接取一段 5，也可以拆成两段 2 和 3；状态保存的是“最多段数”，因此取 2。

C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, a, b, c;
    cin >> n >> a >> b >> c;
    vector<int> dp(n + 1, -1);
    dp[0] = 0;
    for (int len = 1; len <= n; ++len) {
        for (int piece : {a, b, c}) {
            if (len >= piece && dp[len - piece] != -1) {
                dp[len] = max(dp[len], dp[len - piece] + 1);
            }
        }
    }
    cout << dp[n] << '\n';
}

为什么这个转移不会漏掉最优解

任何合法方案都有最后一段，它必然属于三种允许长度之一。去掉最后一段后，如果剩余方案不是对应前驱的最优方案，就可以替换成更优方案，使总段数进一步增加。因此，只需比较三种最后一段所对应的最优前驱。

所有长度为正，前驱下标一定小于当前下标；从小到大计算时，依赖都已完成。每个长度只检查三次，时间为 O(n)，空间为 O(n)。允许长度重复也不影响答案，只会重复检查同一候选。

3. Boredom：状态轴为什么不是数组下标

每次选一个数值 x 获得 x 分，并删除所有值为 x-1 和 x+1 的元素。相同数值的其他元素仍然存在。输入最多有十万个数，每个值介于 1 和十万之间。

冲突取决于数值相差一，与两个元素在原数组里是否挨着无关。因此，应该先统计 count[x]，把每个值的总收益记为 gain[x] = x * count[x]。

一旦决定选择值 x，它的所有副本都可以依次选走：继续选同值不会引入新的冲突，而且收益为正。原问题就变成：从数轴上选择一些互不相邻的位置，让总权重最大。

收益最大的值也不能盲目先拿

考虑数组 [2, 2, 3, 3, 3, 4, 4]。各值的总收益为 4、9、8。优先拿收益最大的 3，只能得到 9；选择 2 和 4 则能得到 12。

局部最大收益会同时排斥左右两侧，失去的机会可能更大。

定义状态，拆成互斥的两类

令 dp[v] 表示：只允许使用数值 1…v 时，最多能得多少分。

对值 v 的选择 前面还能选择的范围 候选收益
不选 v 1…v-1 dp[v-1]
选择所有 v 1…v-2 dp[v-2] + gain[v]

所以 dp[v] = max(dp[v-1], dp[v-2] + gain[v])，边界为 dp[0]=0、dp[1]=gain[1]。

用上面的例子逐步计算：

v gain[v] 跳过 v 选择 v dp[v]
1 0 0 0 0
2 4 0 4 4
3 9 4 9 9
4 8 9 4+8 12

这里的 0 不是“不可达”。即使一个值都不选，也能合法得到 0 分；它与上一题的初始化语义完全不同。

C++17 实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;
    vector<long long> gain(100001, 0);
    int maximum = 0;
    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        gain[x] += x;
        maximum = max(maximum, x);
    }

    vector<long long> dp(maximum + 1, 0);
    dp[1] = gain[1];  // 题目保证至少一个数，且所有数为正
    for (int v = 2; v <= maximum; ++v) {
        dp[v] = max(dp[v - 1], dp[v - 2] + gain[v]);
    }
    cout << dp[maximum] << '\n';
}

每个最优方案要么不选 v，要么选择 v 并排除 v-1；两类互斥且覆盖所有方案。对两个前驱应用同样结论，就得到归纳证明。

设值域上限为 V=100000，统计和初始化加递推的时间为 O(n+V)，空间为 O(V)。总收益可能达到 10^10，必须使用 long long。后续可以用两个变量压缩 DP 数组，但先保留完整状态更利于调试。

4. 把状态写成一句能被检查的话

检查项 Cut Ribbon Boredom
状态轴 已拼出的精确长度 允许使用的数值上界
最后一个决策 最后一段取哪种长度 当前值选还是不选
空方案是否合法 仅长度 0 合法 任意前缀均可不选
不可达如何表示 -1，且必须检查前驱 不需要单独标记
计算顺序 长度从小到大 数值从小到大

遇到新题时，先补全“在什么限制下，记录什么最优值”。然后检查不同历史是否真的能合并：如果未来还依赖一个没有记录的条件，当前状态就不够用。

5. 自测与继续练习

可以用下面几组输入主动检查边界：

  • Cut Ribbon：1 1 1 1 应得 1；7 2 3 5 应得 3；7 2 4 7 应得 1，检查算法是否错误接受剩余长度。
  • Boredom：只有一个 7，应得 7；[1,1,2,2,3,3] 应得 8；十万个 100000 应得 10000000000，检查溢出。

更可靠的本地方法是小规模对拍：剪绳题枚举三种段的数量；删数题枚举不同数值的所有子集，排除包含相邻数值的子集，再与 DP 比较。这样的穷举检查与快速算法采用不同思路，更容易发现共同样例之外的问题。

拓展练习：让 Cut Ribbon 同时输出一组切法。每次改善 dp[len] 时记录最后一段长度，最后从 n 向 0 回溯。再思考：如果改问“不同切法有多少种”，顺序是否算不同方案？状态含义一变，循环顺序和去重方法也可能要变。

回到 算法练习路径 可以对照贪心和二分；如果对 AI 中“多找几个候选再验证”感兴趣，可以继续读 大模型推理时计算，比较精确算法证明与统计验证的差别。