關鍵字：
Dilworth theorem / partially ordered set / non-strict partial order / 偏序 / 非嚴格偏序 / 自反偏序
這篇文章是為了把之前做的筆記整理成電子版本，順便幫助自己之後複習，還請多多指教！
研讀較抽象的算法或概念，最害怕不知道能幹嘛，所以我在開頭這邊先給出一個題目以及簡述，才開始介紹什麼是偏序關係、偏序集以及Dilworth theorem，最後，再使用該定理來解決開頭的問題，以及給出其他例題，以下正文開始。
傳送門：105學年度資訊學科能力決賽第五題-直昇機抓寶
題目簡述：
在N×N方格上，原點終點分別為最左下、右上角的方格，從原點開始只能往右或往上移動，在每個橫排皆有唯一連續區間，求原點移動到終點最多可通過幾個區間？
N ≤ 800,000 看這Ｎ這麼大，N 平方掃過去的做法可以先收一收了。
input output 5 3 2 2 1 1 0 0 2 2 4 4
已經知道偏序關係的同學可以跳過 偏序 這節，想直接看詳解請用力下拉。
偏序
我們先假設Ａ是個集合（例：整數集合），定義一個二元關係Ｐ（例：≤，左右各需要一個運算元稱為二元），如果Ｐ滿足：
- reflexivity (自反性)
- antisymmetry (反對稱性）
- transitivity（傳遞性）
則我們說，Ｐ為Ａ的一個偏序關係
（本文的偏序，皆是以非嚴格偏序、自反偏序來說明）
reflexivity 自反性
∀a ∈ A , （a,a） ∈ P
（a,a）∈ P 是指（a,a）滿足Ｐ關係。
舉個例子：
- Ａ是 整數集合
- ａ是 整數集合中的任意一個元素，其實就是整數的意思啦
- Ｐ是 小於等於關係 （≤）
則（a,a）∈Ｐ，因為 ａ≤ａ 成立
再舉個例子：
- ａ是 正整數
- Ｐ是 整除
則（a,a）∈Ｐ，因為 ａ整除ａ 成立
我們總結一下偏序關係中，自反性的意思如下：
若Ｐ為Ａ的一個偏序關係，則對於所有Ａ內的元素ａ，（a,a）都 必須 滿足Ｐ關係。
補充：∀ 是指對於所有集合內的元素，英文為for all
antisymmetry 反對稱性
∀a ∈ A , ∀b ∈ A，if (a,b)∈P and (b,a)∈P，then a=b
（a,b）∈Ｐ內的ａ與ｂ不可對調，除非他們相等。
繼續用剛剛的例子：
- ａ,ｂ是 整數
- Ｐ是 小於等於
（a,b）∈Ｐ → ａ≤ｂ
（b,a）∈Ｐ → ｂ≤ａ
很明顯了吧！？，除非ａ＝ｂ否則不成立。
值得一提的是，if(a,b)∈P 千萬別誤會成是任意(a,b)都∈Ｐ！
transitivity 傳遞性
∀a ∈ A , ∀b ∈ A , ∀c ∈ A，if (a,b)∈P and (b,c)∈P，then (a,c)∈P
用反對稱性的代換一下，大概就懂這個意思了吧ＸＤ
小整理
對於集合Ａ，某二元關係Ｐ如果滿足自反性、反對稱性、傳遞性，則Ｐ為集合Ａ的一個偏序關係。
太拗口？？
反正拿整數以及小於等於來思考一下就好啦，運算兩邊可相同、兩邊不可任意交換、可推導（ａ≤ｂ,ｂ≤ｃ→ａ≤ｃ）！
偏序集、可比、鏈
終於講完偏序關係，這裡當作大家都已經理解了(?)，我們來繼續定義一些東西
首先是偏序集合，再來是可比不可比，最後解釋鏈與反鏈。
偏序集合 poset
偏序集 ＝ 偏序集合 ＝ partially ordered set = poset
偏序集 ＝ 集合 ＋ 集合的一個偏序關係 ＝（Ａ, Ｐ）
舉個例子，剛剛我們用來講解偏序關係的小於等於以及整數集合，可以表示為（𝚭, ≤）。
可比 comparable
在偏序集內任意兩元素ａ,ｂ，滿足（a,b）∈Ｐ或（b,a）∈Ｐ，則稱ａ,ｂ可比（comparable）， 否則不可比 （incomparable）
舉個例子：
poset（ 𝚭, 整除 ）內，元素２,４可比，元素３,４不可比，因為滿足（2,4）∈Ｐ，２整除４成立；而３整除４ 或 ４整除３ 都不成立，所以３,４不可比。
再舉個例子：
（𝚭, ≤）內任兩元素可比，思考看看吧！
（對Tree不熟先去惡補一下 或跳往chain）
再舉個比較另類的例子（Ａ,Ｐ）
- Ａ集合 = 有根（序）樹上的所有節點
- Ｐ關係 = ａ在以ｂ為根的子樹內
（請自行驗證Ｐ為Ａ的偏序關係）
則對於樹上任一點ｖ，ｖ與所有祖先及子樹成員可比，與所有祖先的子樹（不包括ｖ所在的子樹）成員不可比。
鏈 chain
我比較常聽到人家唸chain，而不稱鏈，所以這邊我們都使用 chain 來稱呼～
chain：若集合內任兩元素可比，稱為 chain。
antichain：若集合內任兩元素不可比，稱為 antichain。
延續可比不可比所舉的例子來說明 chain / antichain
- （𝚭, 整除）
chain：｛１,２,４,８｝antichain：｛３,４,５｝ - （Ａ,Ｐ）
chain：｛ｖ以及所有祖先 ｝ antichain：｛ｖ的子節點 ｝
Dilworth theory
有了以上各種定義，我們可以在上面堆出一個定理
In any finite poset, the minimum number of chains cover equals the maximum size of an antichain
太抽象的東西看英文比較好理解ＸＤ，有看沒有懂的請繼續往下走
定理所說的是，令（Ｓ,Ｐ）是一個偏序集且Ｓ是有限集合（正整數集合不是個有限集合），minimum chains cover 會等同於最大 antichain 的 size
minimun chains cover：把所有集合內元素 都涵蓋在內所需要最少的 chain 的數量。或者也可以這麼理解，集合最少會被切割成幾個 chain ，無法再更少。
如果要將偏序集分割成最少的 chain ，則 chain 的數量會與集合內最大（元素最多）的 antichain 大小相等。
一句話，最大反鏈等於最小鏈覆蓋
當然，最大鏈等於最小反鏈覆蓋也是成立的。
到這裡我們已經把精華解釋完畢，至於這個定理是如何成立的，建議自行先推導看看。
key point : 集合要切成 chains 需把不可比的分開。
另外，雖然本文說的是自反偏序集，但此定理偏序集都適用，只需要是有限集合。
還記得開頭的題目嗎？
在N×N方格上，原點終點分別為最左下、右上角的方格，從原點開始只能往右或往上移動，在每個橫排皆有唯一連續區間，求原點移動到終點最多可通過幾個區間？
先觀察題目，簡單地發現一些特點：
- 一進入區間立刻往上走才是最佳解，所以通過區間的位置一定是某個經過的區間左界，當然也可能是目前這層的區間左界
- 上方的區間右界如果在目前位置的左方則不可能經過該區間
看起來很正常的兩點就是關鍵，如果下方出現無法理解的邏輯請回來複習這兩點
第一點保證了我們在紀錄最佳路徑時，只需透過經過的左界來維護即可。
具體來說每次要經過區間時，如果該區間左界在目前位置的左邊則不予理會（等於往上走就剛好在一個區間內），否則更新目前位置為該區間左界（等於往上又往右走才經過該區間）。
觀察到這邊已經可以直接拿線段樹砸題目ＡＣ了，不過我們抽象化這個問題可能會更有趣！
現在來定義一下 poset （Ａ,Ｐ）吧
- 集合Ａ = 每個 row 的區間（不過只紀錄左界）
- Ｐ關係 = ａ的目前位置可以經過ｂ區間
那麽我們問題所求，其實就是找最大的 chain ！
心裡默念：最大鏈等於最小反鏈覆蓋
也就是我們也可以選擇求最小 antichain cover
複習一下
antichain：若集合內任兩元素不可比，稱為 antichain。
可比：在偏序集內任意兩元素ａ,ｂ，滿足（a,b）∈Ｐ或（b,a）∈Ｐ，則稱ａ,ｂ可比。
antichain 任兩元素ａｂ不可比在這邊代表 ａ的目前位置無法經過ｂ區間 或 ｂ目前位置無法經過ａ區間。
根據剛剛觀察題目的兩點，我們用區間左界維護每個 antichain 的目前位置，用區間右界判斷該區間能加入哪個 antichain （也就是該區間與哪個 antichain 的目前位置不可比）
判斷要加入哪個 antichain 使用 upper_bound() 最方便，又因為 antichain 的目前位置可能會重複，只能用 multiset ，以下附上AC code + 微註解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <bits/stdc++.h>
using namespace std;
int N, a,b;
multiset<int> s; // 集合內每個元素都是個 antichain
int main(){
cin >> N ;
for(int i=0;i<N;i++){
cin >> a >> b;
auto si = s.upper_bound(b); // 找最靠近的 antichain 來加入
if(si != s.end()) s.erase(si); // 更新 antichain 的目前位置相當於刪除再加入
s.insert(a);
}
printf("%d\n", s.size()); // minimun antichain cover
}
落落長的一篇換幾行短短的code :D
其他題目傳送門
poj 1065 : Wooden Sticks ċȯḋė
poj 1548 : Robots ċȯḋė
poj 3636 : Nested Dolls ċȯḋė
poj 3866 : Exclusive Access 2 ċȯḋė（較難）