算法札记：Dilworth定理及其证明（导弹拦截）

Dilworth定理

想象一下，你正坐在一个防空指挥室里，雷达屏幕上密密麻麻全是敌方导弹的光点，每个导弹都有一个飞行高度。你的任务就是用最少的拦截系统，把这些导弹全部打下来。

但这里有个麻烦的规则：‌每一套拦截系统，它打出的导弹高度必须是一发比一发低，或者至少不能越来越高‌。也就是说，一套系统只能拦截一个“不上升”的高度序列。

问题来了：最少需要多少套系统？

直觉上，我们可能会想用贪心算法：来一枚导弹，就看看现有系统里谁能拦截它，就塞给谁；如果都不行，就新开一套系统。这个方法其实是对的，但它并没有告诉你，这个“最少”的数量到底是由什么决定的。

‌Dilworth定理就像一道闪电，瞬间照亮了答案。‌

定理到底说了什么？

用大白话讲，Dilworth定理在导弹拦截这个场景里，就是说了一句“废话”，但又是一句极其深刻的“废话”：

‌“你最少需要多少套拦截系统，恰好等于你导弹序列里，那个‘最长上升子序列’的长度。”‌

是不是有点绕？别急，我们拆开来看。

• ‌“链”‌：在我们的问题里，就是‌一套拦截系统能拦截的所有导弹‌。因为它们的高度是“不上升”的，所以它们之间可以互相比较（谁高谁低），这就构成了一条“链”。
• ‌“反链”‌：就是‌一串导弹，它们的高度是严格上升的‌。为什么叫“反链”？因为在这串导弹里，任意两枚都无法被同一套系统拦截（后一枚总比前一枚高，违反了“不高于前一发”的规则），它们之间“不可比较”，所以叫“反链”。

现在，定理的核心就变成了：

‌“最少链的划分（最少系统数）” = “最长反链的长度（最长上升子序列长度）”‌

用例子说话，一看就懂

假设导弹按顺序飞来，高度是：[3, 1, 4, 2]

我们先来找找它的‌最长上升子序列‌。
可能的上升序列有：

• [3, 4]
• [1, 4]
• [1, 2]

最长上升子序列的长度是 ‌2‌（比如[1, 2]或[3, 4]）。

根据Dilworth定理，我们最少需要的拦截系统数量，就应该等于这个长度，也就是 ‌2套‌。

我们来验证一下，看看是不是真的需要2套系统：

• ‌第1套系统‌：拦截了第1枚导弹（高度3），然后它只能拦截高度 ≤ 3 的导弹。第2枚导弹高度1，可以拦截。所以这套系统拦截了[3, 1]。
• ‌第2套系统‌：第3枚导弹高度4，第1套系统刚拦截了高度1，没法拦截高度4（因为4 > 1，违反了不上升规则）。所以必须新开一套系统，拦截高度4。接着第4枚导弹高度2，它 ≤ 4，可以被第2套系统拦截。所以这套系统拦截了[4, 2]。

你看，正好2套系统，一套不多，一套不少。

为什么这个定理如此神奇？

它的美妙之处在于，它把一个‌“最少需要多少”的划分问题‌，巧妙地转化成了一个‌“最长能有多长”的寻找问题‌。

你不需要费尽心思去模拟怎么分配系统，只需要找出那个最长的、节节攀升的导弹序列，它的长度，就是你要的答案。因为在这个最长上升序列里的每一枚导弹，都注定无法和序列里的其他任何一枚共享同一套拦截系统，它们就像一群死对头，必须一人一间牢房。所以，这个最长上升序列的长度，就是你牢房数量的下限，而Dilworth定理告诉你，这个下限恰好就能达到！

证明

准备工作：把概念精确化

在开始证明前，我们先把“导弹拦截”里的直觉，翻译成精确的数学语言。

我们有一个‌有限偏序集‌ (P,≤)。这里的“偏序关系” ≤ 满足自反性、反对称性和传递性。

• ‌链‌：P 的一个子集，其中任意两个元素都是可比的。在导弹问题中，一套系统拦截的导弹序列（高度不上升）就是一条链。
• ‌反链‌：P 的一个子集，其中任意两个不同元素都不可比。在导弹问题中，一个高度严格上升的导弹序列就是一条反链。
• ‌链划分‌：把 P 分成若干条互不相交的链，这些链的并集就是整个 P。我们关心的是‌最小链划分数‌，即最少需要多少条链才能覆盖整个 P。
• ‌最长反链‌：P 中包含元素最多的反链，其元素个数记为 w。

我们的目标是证明：‌最小链划分数 = 最长反链的元素个数 w‌。

第一步：证明“最小链划分数 ≥ 最长反链长度 w”

这一步非常直观，是证明的“容易”部分。

1. 设 A 是 P 中一个元素个数为 w 的最长反链。
2. 根据反链的定义，A 中的任意两个元素都不可比。
3. 这意味着，在任何一个链划分中，A 中的任意两个元素都‌不能‌被放入同一条链（因为同一条链里的元素必须两两可比）。
4. 因此，A 中的 w 个元素，每一个都必须独占一条不同的链。
5. 所以，任何链划分至少需要 w 条链。那么，最小链划分数也必然大于或等于 w。

📝 ‌结论‌：最小链划分数 ≥w。

第二步：证明“最小链划分数 ≤ 最长反链长度 w”

这是证明的核心和难点。我们需要证明，确实存在一种划分方法，恰好只用 w 条链就能覆盖整个 P。我们对偏序集 P 的元素个数 ∣P∣ 进行‌数学归纳‌。

‌归纳基础‌：当 ∣P∣=1 时，结论显然成立。此时最长反链长度 w=1，整个集合本身既是1条链，也是1个反链，用1条链即可覆盖。

‌归纳假设‌：假设对于所有元素个数小于 ∣P∣ 的有限偏序集，定理成立。

‌归纳步骤‌：现在考虑元素个数为 ∣P∣ 的偏序集。设 A 是 P 的一条最长反链，长度为 w。我们分两种情况讨论。

情况一：存在一条最长反链 A，它既不是 P 的所有极大元的集合，也不是 P 的所有极小元的集合

这意味着，在 A 之外，既有比 A 中某些元素大的元素，也有比 A 中某些元素小的元素。我们定义两个集合：

• ‌上集‌ U(A)={x∈P∣∃a∈A 使得 a<x} （严格大于 A 中某元素的元素集合）
• ‌下集‌ D(A)={x∈P∣∃a∈A 使得 x<a} （严格小于 A 中某元素的元素集合）

由于 A 是反链，且不是全部极大元或极小元，可以证明 U(A) 和 D(A) 都非空，且 P=A∪U(A)∪D(A)，并且这三个集合两两不相交。

现在，我们考虑两个更小的偏序集：P1​=A∪D(A) 和 P2​=A∪U(A)。它们的元素个数都严格小于 ∣P∣。

1. 在 P1​ 中，A 仍然是它的最长反链（因为 U(A) 中的元素都比 A 中某元素大，不会和 A 形成更大的反链）。根据归纳假设，P1​ 可以被划分为 w 条链，且由于 A 是反链，这 w 条链的极大元恰好就是 A 中的 w 个元素。
2. 同理，在 P2​ 中，A 也是它的最长反链。根据归纳假设，P2​ 也可以被划分为 w 条链，且这 w 条链的极小元恰好就是 A 中的 w 个元素。

现在，我们把这两组链“对接”起来：对于 A 中的每一个元素 ai​，我们把 P1​ 中以 ai​ 为极大元的链，和 P2​ 中以 ai​ 为极小元的链，在 ai​ 处连接成一条新链。这样，我们就得到了 w 条链，它们完整地覆盖了整个 P。

✅ 情况一得证。

情况二：对于每一条最长反链 A，它要么全是极大元，要么全是极小元

这意味着，最长反链 A 要么“漂浮”在 P 的最顶层，要么“沉在”最底层。

1. 我们可以在 P 中选出一个极小元 x 和一个极大元 y，并且满足 x≤y（这样的 x,y 一定存在，比如从 x 出发向上走一条链到某个极大元）。
2. 从 P 中移除 x 和 y，得到更小的偏序集 P′=P∖{x,y}。
3. 关键点来了：P′P′ 的最长反链长度一定是 w−1w−1。为什么？因为 PP 的任何一条最长反链 AA（长度为 ww），根据我们的假设，它要么全是极大元，要么全是极小元。如果 AA 全是极大元，那么它一定包含 yy，移除 yy 后 AA 的长度减1；如果 AA 全是极小元，那么它一定包含 xx，移除 xx 后 AA 的长度也减1。所以 P′P′ 中不可能再有长度为 ww 的反链。
4. 根据归纳假设，P′P′ 可以被划分为 w−1w−1 条链。
5. 我们把 {x,y} 这条长度为2的链（因为 x≤y）加到刚才的划分中，就得到了 PP 的一个链划分，总共是 (w−1)+1=w 条链。

✅ 情况二得证。

最终结论

综合第一步和第二步的证明，我们得到：

• 最小链划分数 ≥w
• 最小链划分数 ≤w

因此，两者必须相等。‌Dilworth定理得证‌：对于任意有限偏序集，其最小链划分数等于其最长反链的元素个数。

例题

除了经典的导弹拦截，Dilworth定理在算法竞赛中还有很多巧妙的应用。它的核心思想就是把一个“最少划分”的问题，转化为一个“最长序列”的求解问题，往往能让看似复杂的题目豁然开朗。

这里有几道典型的算法题，正好可以帮你练练手，加深理解。

经典必刷：导弹拦截系列

这是Dilworth定理最直接的应用，也是理解定理的绝佳起点。

‌题目‌：给定一个导弹高度序列，一套系统每次拦截的高度不能高于前一次。求：

1. 一套系统最多能拦截多少导弹？
2. 最少需要多少套系统才能全部拦截？

‌定理应用‌：

• ‌第一问‌：求‌最长不上升子序列‌的长度。
• ‌第二问‌：根据定理，最少系统数等于序列中最长上升子序列的长度。因为每一枚在上升序列中的导弹，都注定无法被同一套系统拦截，必须“另起炉灶”。

‌算法优化‌：这题通常数据量不小，用传统的动态规划（O(n²)）可能会超时。标准解法是用‌贪心+二分查找‌，将复杂度优化到O(n log n)。维护一个数组d，d[i]表示长度为i的上升子序列的最小末尾元素，通过二分查找来更新，非常巧妙。

思维进阶：字符串染色问题

这道题来自Codeforces，是Dilworth定理更隐晦但有趣的应用。

‌题目‌：给一个字符串，你可以给每个字符染色。规定只有相邻且颜色不同的字符才能交换位置。求最少需要多少种颜色，使得经过若干次交换后，字符串能按字典序从小到大排列，并输出染色方案。

‌定理应用‌：

• ‌转化问题‌：题目允许交换，最终要求有序。可以发现，‌颜色相同的字符之间不能交换，因此它们在原字符串中构成的子序列，必须已经是非递减的‌。换句话说，同一种颜色对应一个非递减子序列。
• ‌核心结论‌：问题就变成了：最少需要多少种颜色，才能将字符串划分成若干个非递减子序列？根据Dilworth定理，这个最小划分数，就等于字符串中‌最长递减子序列‌的长度。
• ‌构造方案‌：每个字符的颜色编号，可以直接等于以该字符结尾的最长递减子序列的长度。

图论模型：最小链覆盖与路径覆盖

Dilworth定理在图论中也有重要地位，常用来解决“覆盖”问题。

‌最小链覆盖‌：在一个有向无环图中，用最少的、可以相交的路径覆盖所有点。这个问题可以通过‌Floyd传递闭包‌，将“可以相交”转化为“不可相交”，然后用‌二分图最大匹配‌来求解。而Dilworth定理则从另一个角度揭示：这个最小链覆盖数，等于图中最长反链的大小。

‌例题‌：比如，给定一些任务及其先后依赖关系，求最少需要多少条流水线才能完成所有任务，就可以建模为最小链覆盖问题。

更多应用场景

Dilworth定理的应用远不止于此，只要你能将问题建模为偏序集，它就可能派上用场：

• ‌任务调度‌：有一堆任务，每个有开始和结束时间，求最少需要多少台机器才能全部完成。如果任务间有偏序关系，就可以用定理分析。
• ‌嵌套问题‌：比如俄罗斯套娃信封问题，求最多能嵌套多少个，以及最少能分成多少组互不嵌套的信封。
• ‌序列划分‌：任何将序列划分成若干个单调子序列的问题，都可以考虑用Dilworth定理转化为求对偶单调子序列的长度。

这些题目在洛谷、Codeforces、AcWing等在线评测平台上都能找到，你可以搜索“导弹拦截”、“最小链覆盖”、“Dilworth定理”等关键词来练习。理解这个定理的精髓，你会发现很多看似复杂的组合优化问题，都能迎刃而解。