Dilworth定理

偏序关系

设$R$是集合$A$的一个二元关系，若$R$满足：
1.自反性:$\forall x\in A$，有$xRx$
2.反对称性：$\forall x,y\in A$，若$xRy,yRx$，则$x=y$
3.传递性：$\forall x,y,z\in A$，若$xRy,yRz$，则$xRz$

则称$R$为$A$上的偏序关系，通常记作$⪯$

偏序集

偏序集合（Partially ordered set，Poset）是数学中，特别是序理论中，指配备了偏序关系的集合

链

设若干元素构成一个集合，那么这个集合是链当且仅当这个集合的所有元素两两可比

反链

对一个集合，它是反链当且仅当这个集合里的元素两两不可比

极大元

设偏序集$A$，$x\in A$，$\nexists y\in A,x\ne y,s.t.x⪯y$,则$x$为极大元

Dilworth定理

设$P$是一个有限的偏序集，则
min⁡{m∣∃链C1,C2,⋯,Cm,P=∪i=1mCi}=max⁡{∣A∣:A是反链}\min\left\{m|\exists 链C_1,C_2,\cdots,C_m,P = \cup_{i=1}^{m}C_i\right\}=\max\left\{\left|A\right|:A是反链\right\} min{m∣∃链C1​,C2​,⋯,Cm​,P=∪i=1m​Ci​}=max{∣A∣:A是反链}

偏序集能划分成的最少的链的个数与最大反链的元素个数相等

证明：
首先证明max⁡{∣A∣}≤min⁡{m}\max\left\{\left|A\right|\right\}\le \min\left\{m\right\}max{∣A∣}≤min{m}
假设max⁡{∣A∣}>min⁡{m}\max\left\{\left|A\right|\right\}> \min\left\{m\right\}max{∣A∣}>min{m}
存在$\exists x,y\in A,s.t.x,y\in C_i$
说明$x,y$是可比的，与反链定义矛盾

同时我们也可以得出$\left|C_i\cap A\right|=1$

接着我们对$\left|P\right|$进行归纳，来证明可以取等
当$\left|P\right|=0,1$时，显然成立
假设$\left|P\right|=k$时成立
当$\left|P\right|=k+1$时
设最大反链长度是$m$
最长的链是C={x1,x2,⋯,xp}C=\left\{x_1,x_2,\cdots, x_p\right\}C={x1​,x2​,⋯,xp​}，满足$x_1⪯x_2⪯\cdots ⪯x_p$
换句话说我们不能再往$C$中增加元素，也可以得出$x_p$是极大元

接下来分类讨论
当$P\backslash C$的每一条反链都的元素个数$\le m-1$
由于$\left|P\backslash C\right|<k$，由归纳$P\backslash C$可以划分为$m-1$个链，即$P\backslash C={\cup }_{i=1}^m{C}_i$
那么$P$可以划分为$P=C\cup {\cup }_{i=1}^m{C}_i$，结论成立

当$P\backslash C$中存在反链A={a1,a2,⋯,am}A = \left\{a_1,a_2,\cdots,a_m\right\}A={a1​,a2​,⋯,am​}时

令
P−={x∈P∣∃i,x⪯ai}P+={x∈P∣∃i,ai⪯x}P^{-} = \left\{x\in P\mid \exists i ,x \preceq a_i\right\}\\ P^{+} = \left\{x\in P\mid \exists i ,a_i\preceq x\right\}\\ P−={x∈P∣∃i,x⪯ai​}P+={x∈P∣∃i,ai​⪯x}

我们可以得出
1.$P=P^{-}\cup P^{+}$（否则存在元素与反链中的元素不可比，则这条反链不是最大的，矛盾）
2.$P^{-}\cap P^{+}=A$ （因为$a_i⪯a_i$,所以$a_i\in P^{-},a_i\in P^{+}$）
3.$x_p\notin P^{-}$(反则$x_p$不是极大元)

$A$是$P^{-}$的一条最大反链，由归纳$P^{-}$可以划分为$m$条链$C_1^{-1},C_2^{-},\cdots ,C_m^{-}$
由于$\left|A\cap C_i^{-}\right|=1$，不妨假设$a_i\in C_i^{-}$
我们可以得出，$a_i$是$C_i^{-}$的最大元
（否则,不妨假设$x\in C_i^{-}$满足$a_i⪯x$，由于$x\in P^{-}$，$\exists a_j,s.t.x⪯a_j(a_i\ne a_j)$,进而$a_i⪯x⪯a_j$,与反链定义矛盾）

同理$P^{+}$也可以划分为$C_1^{+},C_2^{+},\cdots ,C_m^{+}$，$a_i$是$C_i^{+}$的极小元
令$C_i=C_i^{-}\cup C_i^{+}$,则$P$可以划分为$C_1,C_2,\cdots ,C_m$这$m$条链
得证

洛谷P1020

最长不上升子序列
设$A=[a_1,a_2,\cdots ,a_n]$
定义偏序关系$a_i⪯a_j\iff i\le j且a_i\ge a_j$（容易验证满足偏序关系）

这个偏序关系就对应了最长不上升序列
最长不上升序列就是在求最长的链
划分最长不上升序列的个数最少为最长上升子序列长度

#include<cstdio>
#include<algorithm>
#include<functional>const int N = 1e5 + 5;int dp1[N];
int dp2[N];int main() {bool flag = false;int t, idx, ans1 = 1, ans2 = 1;while (~scanf("%d", &t)) {if (!flag) {flag = true;dp1[1] = dp2[1] = t;continue;}if (dp1[ans1] >= t) {++ans1;dp1[ans1] = t;}else {int idx = std::upper_bound(dp1 + 1, dp1 + 1 + ans1, t, std::greater<int>()) - dp1;dp1[idx] = t;}if (t > dp2[ans2]) {++ans2;dp2[ans2] = t;}else {int idx = std::lower_bound(dp2 + 1, dp2 + 1 + ans2, t) - dp2;dp2[idx] = t;}}printf("%d\n%d\n", ans1, ans2);return 0;
}

https://www.cnblogs.com/itlqs/p/6636222.html
https://cmwqf.github.io/2019/12/17/%E6%B5%85%E8%B0%88Dilworth%E5%AE%9A%E7%90%86/
https://www.math.cmu.edu/~af1p/Teaching/Combinatorics/F03/Class14.pdf