偏序集
定义
定义偏序集是由一个集合 $S$ 与一个二元关系 $\le$ 组成的二元组 $O=(S,\le)$，满足：
自反性：对于任意元素 $a\in S$，有 $a \le a$
反对称性：对于任意元素 $a,b\in S$，若 $a\le b$ 且 $b\le a$，则 $a=b$
传递性：对于任意元素 $a,b,c\in S$，若 $a\le b$ 且 $b\le c$，则 $a\le b\le c$
偏序关系：我们称一个偏序集 $O=(S,\le)$ 中的偏序关系为二元关系 $\le$
链：对于一个偏序集 $O=(S,\le)$，一个由 $O$ 的元素组成的非重序列 $a_i$ 满足 $a_i<a_{i+1}$ 称为 $O$ 的一条链
反链：对于一个偏序集 $O=(S,\le)$，一个由 $O$ 的元素组成的集合满足集合中任意元素 $a,b$ 都不满足 $a\le b$，那么这个集合是 $O$ 的一条反链
Dilworth定理
定理1：令 $O=(S,\le)$ 为一有限偏序集，$O$ 的最小反链划分等于 $O$ 的最长链长度
定理2：令 $O=(S,\le)$ 为一有限偏序集，$O$ 的最小链划分等于 $O$ 的最长反链长度
推论1：大小为 $nm+1$ 的偏序集，要么有长度为 $n+1$ 的链，要么有长度为 $m+1$ 的反链
推论2：长度为 $n$ 的数列，要么有长度至少为 $\sqrt n$ 的非严格上升子序列，要么有长度至少为 $\sqrt n$ 的非严格下降子序列
推论3(存疑)：给定一张有向无环图，定义这张图上的链覆盖为点 $i$ 要被覆盖至少 $a_i$ 次，则最小链覆盖等于最大权独立集
例题
简要题意：给定一张 $n\times m$ 的网格图，从左上角出发，只能向右或者向下走，每个点有一个权值 $a_{i,j}$，每次经过一个点可以使权值减一，求至少走几次才能使所有点的权值为 $0$
$n,m\le 1000,a_{i,j}\le 10^6$
简要题解：我们有结论，$DAG$ 上最小链覆盖等于最大独立集，这里我们可以看做每个点需要覆盖 $a_{i,j}$ 次，本质上是一样的
所以我们直接令 $f[i][j]$ 表示从 $(i,j)$ 到 $(1,n)$ 这个矩形的最大权独立集，然后做 $dp$ 即可，时间复杂度 $O(nm)$