偏序集的两个定理：
定理1 令（X,≤）是一个有限偏序集，并令r是其最大链的大小。则X可以被划分成r个但不能再少的反链。
其对偶定理称为Dilworth定理：
定理2 令（X,≤）是一个有限偏序集，并令m是反链的最大的大小。则X可以被划分成m个但不能再少的链。
说白了就是 链的最少划分数=反链的最长长度
相关的题目有pku 1065，pku 3636，pku 1548。
这三个题目可以归结为：
　　给定n个二元组(x, y)，问存在最少多少个划分使得每个划分里面的二元组都满足x1 <= x2并且y1 <= y2。
　　如果定义x1 <= x2 && y1 <= y2为偏序关系的话，那么问题就转化成求这个集合的链的最少划分数。可以通过找最长反链长度来解决，这里的反链关系是x1 > x2 || y1 > y2。如果把n个二元组按照x递增排序，相同的x按照y递增排序，那么我们只需对y找到一个最长递减子序列就是所求的答案，复杂度O(nlogn)。对于相同的x之所以按照y递增排序是因为这里偏序关系带等号，这样相同的x其实可以划分到一起，把y按照递增排序就可以使得相同的x最多只选择一个y。
　　还有的题目要求满足x1 < x2 && y1 < y2，这就需要把偏序关系相应修改。修改之后对于相同的x，每一个都会被划分到不同的集合（因为相等是不满足偏序关系的），所以这里的排序关系要改一下，x相同的y要按照降序排列，这样求一个最长不递增子序列就是答案，y递减保证可能会有多个x相同的二元组选入到结果中。
　　可惜对于贪心做法的正确性依然想不出来>.<