感觉有些时候比较有用。
1.内容
先说明偏序集。我们定义两个元素的比较关系。可以存在部分元素无法比较。需要满足以下三个条件：
1.自反性，$\forall a\in S$，有 $a\le a$.。
2.对称性，$\forall a,b\in S$，若 $a\le b$，有 $b\ge a$。
3.传递性，$\forall a,b,c\in S$，若 $a\le b,b\le c$，有 $a\le c$。
我们将偏序集中的元素按照比较关系建图，容易发现会得到一张 DAG。而最小链划分就是将 DAG 划分成最少条链。反链为集合中一个一集满足该子集中所有元素都无法比较，其长度即为集合大小。
容易发现最小链剖分，直接求是不好求的。$\text{Dilworth}$ 定理描述的就是其与反链的关系：
偏序集上最小链划分中链的数量等于其反链长度的最大值。
2.例题
1.P1020 [NOIP1999 普及组] 导弹拦截
关于第二问的解法。比较简单的是贪心。但是可以从 $\text{Dilworth}$ 定理的角度思考。
对于每一个位置用一个二元组 $(x,y)$，其中 $x$ 代表该位置的下标，$y$ 表示高度。定义 $(x_1,y_1)\le (x_2,y_2)$ 当且仅当 $x_1\le x_2,y_1\ge y_2$。一个最长上升子序列对应的就是 DAG 上的一条链，于是就转化为最小链剖分的问题，而反链就是两两满足 $x_1< x_2,y_2< y_2$ 的元素的集合。所以答案就是最长上升子序列。
2.P3974 [TJOI2015] 组合数学
还是考虑建立偏序关系。对于每个位置设 $(x,y)$ 表示其坐标。定义 $(x_1,y_1)\le (x_2,y_2)$ 当且仅当 $x_1\le x_2,y_1\le y_2$。并且将每个位置的权值 $v_{i,j}$ 拆成 $v_{i,j}$ 个点。求的就是 DAG 上的最小链剖分。即满足 $x_1< x_2,y_1< y_2$ 的集合大小的最大值。从右下角到左上角进行 DP 即可求出。