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