Dilworth定理

狄尔沃斯定理(Dilworth's theorem)亦称偏序集分解定理，其定义是：对于任意有限偏序集，其最大反链中元素的数目必等于最小链划分中链的数目。对偶形式也成立：对于任意有限偏序集，其最长链中元素的数目必等于其最小反链划分中反链的数目。
我自己的理解是：对于一个偏序集来说，最大反链的元素个数等于划分成全序集最小个数。

以洛谷P1020为例，求解一套导弹拦截系统最多能拦截导弹的数量，这个其实就是一个简单的LIS；而求解需要多少个导弹拦截系统，就使用Dilworth定理，所有发射的导弹高度构成一个偏序集，导弹链接系统的数量就是全序集的个数，每一个导弹拦截系统下一次拦截高度都不能高于前一次拦截的高度，所以，其反链就是最长不严格上升子序列。