偏序集的兩個定理：
定理1 令（X,≤）是一個有限偏序集，并令r是其最大鏈的大小。則X可以被劃分成r個但不能再少的反鏈。
其對偶定理稱為Dilworth定理：
定理2 令（X,≤）是一個有限偏序集，并令m是反鏈的最大的大小。則X可以被劃分成m個但不能再少的鏈。
說白了就是 鏈的最少劃分數(shù)=反鏈的最長長度
相關(guān)的題目有pku 1065，pku 3636，pku 1548。
這三個題目可以歸結(jié)為：
　　給定n個二元組(x, y)，問存在最少多少個劃分使得每個劃分里面的二元組都滿足x1 <= x2并且y1 <= y2。
　　如果定義x1 <= x2 && y1 <= y2為偏序關(guān)系的話，那么問題就轉(zhuǎn)化成求這個集合的鏈的最少劃分數(shù)。可以通過找最長反鏈長度來解決，這里的反鏈關(guān)系是x1 > x2 || y1 > y2。如果把n個二元組按照x遞增排序，相同的x按照y遞增排序，那么我們只需對y找到一個最長遞減子序列就是所求的答案，復(fù)雜度O(nlogn)。對于相同的x之所以按照y遞增排序是因為這里偏序關(guān)系帶等號，這樣相同的x其實可以劃分到一起，把y按照遞增排序就可以使得相同的x最多只選擇一個y。
　　還有的題目要求滿足x1 < x2 && y1 < y2，這就需要把偏序關(guān)系相應(yīng)修改。修改之后對于相同的x，每一個都會被劃分到不同的集合（因為相等是不滿足偏序關(guān)系的），所以這里的排序關(guān)系要改一下，x相同的y要按照降序排列，這樣求一個最長不遞增子序列就是答案，y遞減保證可能會有多個x相同的二元組選入到結(jié)果中。
　　可惜對于貪心做法的正確性依然想不出來>.<