跳转至

# 序理论

## 引入

序理论是利用二元关系来将「次序」这一概念严格化的数学分支，下面将介绍这一分支的基本定义．

## 定义

### 二元关系

定义

集合 𝑋 X 和集合 𝑌 Y 上的一个 二元关系（binary relation）𝑅 R 定义为元组 (𝑋,𝑌,𝐺(𝑅))(X,Y,G(R))，其中 𝑋 X 称为定义域（domain），𝑌 Y 称为陪域（codomain），𝐺(𝑅) ⊆𝑋 ×𝑌 ={(𝑥,𝑦) :𝑥 ∈𝑋,𝑦 ∈𝑌}G(R)⊆X×Y={(x,y):x∈X,y∈Y} 称为二元关系 𝑅 R 的图（graph）．𝑥 𝑅 𝑦 x R y 成立当且仅当 (𝑥,𝑦) ∈𝐺(𝑅)(x,y)∈G(R)．

若 𝑋 =𝑌 X=Y，则称该二元关系为齐次二元关系（homogeneous relation）或内关系（endorelation）．

若没有特别说明，下文中的二元关系均为齐次二元关系．

例如 𝐍+N+ 上的整除 ∣∣ 和小于等于 ≤≤ 均为二元关系．

我们研究二元关系时，往往会关注其是否具有一些特别的性质．对集合 𝑆 S 上的二元关系 𝑅 R，我们定义如下特殊性质：

1. 自反性（reflexive）：(∀ 𝑎 ∈𝑆) 𝑎 𝑅 𝑎(∀ a∈S) a R a，
2. 反自反性（irreflexive，anti-reflexive）：(∀ 𝑎 ∈𝑆) ¬(𝑎 𝑅 𝑎)(∀ a∈S) ¬(a R a)，
3. 对称性（symmetric）：(∀ 𝑎,𝑏 ∈𝑆) 𝑎 𝑅 𝑏 ⟺ 𝑏 𝑅 𝑎(∀ a,b∈S) a R b⟺b R a，
4. 反对称性（antisymmetric）：(∀ 𝑎,𝑏 ∈𝑆) (𝑎 𝑅 𝑏 ∧𝑏 𝑅 𝑎) ⟹ 𝑎 =𝑏(∀ a,b∈S) (a R b∧b R a)⟹a=b，
5. 非对称性（asymmetric）：(∀ 𝑎,𝑏 ∈𝑆) 𝑎 𝑅 𝑏 ⟹ ¬(𝑏 𝑅 𝑎)(∀ a,b∈S) a R b⟹¬(b R a)，
6. 传递性（transitive）：(∀ 𝑎,𝑏,𝑐 ∈𝑆) (𝑎 𝑅 𝑏 ∧𝑏 𝑅 𝑐) ⟹ 𝑎 𝑅 𝑐(∀ a,b,c∈S) (a R b∧b R c)⟹a R c，
7. 连接性（connected）：(∀ 𝑎,𝑏 ∈𝑆) 𝑎 ≠𝑏 ⟹ (𝑎 𝑅 𝑏 ∨𝑏 𝑅 𝑎)(∀ a,b∈S) a≠b⟹(a R b∨b R a)，
8. 良基性（well-founded）：(∃ 𝑚 ∈𝑆 ≠∅) (∀ 𝑎 ∈𝑆 ∖{𝑚}) ¬(𝑎 𝑅 𝑚)(∃ m∈S≠∅) (∀ a∈S∖{m}) ¬(a R m)（即非空集合 𝑆 S 中有极小元 𝑚 m），
9. 不可比的传递性（transitive of incomparability）：(∀ 𝑎,𝑏,𝑐 ∈𝑆) (¬(𝑎 𝑅 𝑏 ∨𝑏 𝑅 𝑎) ∧¬(𝑏 𝑅 𝑐 ∨𝑐 𝑅 𝑏)) ⟹ ¬(𝑎 𝑅 𝑐 ∨𝑐 𝑅 𝑎)(∀ a,b,c∈S) (¬(a R b∨b R a)∧¬(b R c∨c R b))⟹¬(a R c∨c R a)（若 ¬(𝑎 𝑅 𝑏 ∨𝑏 𝑅 𝑎)¬(a R b∨b R a)，则称 𝑎 a 和 𝑏 b 是不可比的）．

同时我们定义一些特殊的二元关系：

二元关系 | 自反性 | 反自反性 | 对称性 | 反对称性 | 非对称性 | 传递性 | 连接性 | 良基性 | 不可比的传递性
--- | --- | --- | --- | --- | --- | --- | --- | --- | ---
等价关系（equivalence relation） | 有 |  | 有 |  |  | 有 |  |  |
预序（preorder，quasiorder） | 有 |  |  |  |  | 有 |  |  |
偏序（partial order） | 有 |  |  | 有 |  | 有 |  |  |
全序（total order） | 有 |  |  | 有 |  | 有 | 有 |  |
良序（well-order） | 有 |  |  | 有 |  | 有 | 有 | 有 |
严格预序（strict preorder） |  | 有 |  |  |  | 有 |  |  |
严格偏序（strict partial order） |  | 有 |  |  | 有 | 有 |  |  |
严格弱序（strict weak order） |  | 有 |  |  | 有 | 有 |  |  | 有
严格全序（strict total order） |  | 有 |  |  | 有 | 有 | 有 |  |

### 关系间的运算

对集合 𝑋 X 和集合 𝑌 Y 上的二元关系 𝑅 R 和 𝑆 S，我们可以定义如下运算：

1. 𝑅 R 和 𝑆 S 的并 𝑅 ∪𝑆 R∪S 满足 𝐺(𝑅 ∪𝑆) :={(𝑥,𝑦) :𝑥 𝑅 𝑦 ∨𝑥 𝑆 𝑦}G(R∪S):={(x,y):x R y∨x S y}（如 ≤≤ 是 << 和 == 的并），
2. 𝑅 R 和 𝑆 S 的交 𝑅 ∩𝑆 R∩S 满足 𝐺(𝑅 ∩𝑆) :={(𝑥,𝑦) :𝑥 𝑅 𝑦 ∧𝑥 𝑆 𝑦}G(R∩S):={(x,y):x R y∧x S y}，
3. 𝑅 R 的补 ¯𝑅 R¯ 满足 𝐺(¯𝑅) :={(𝑥,𝑦) :¬(𝑥 𝑅 𝑦)}G(R¯):={(x,y):¬(x R y)}，
4. 𝑅 R 的对偶 𝑅 𝑇 R T 满足 𝐺(𝑅 𝑇) :={(𝑦,𝑥) :𝑥 𝑅 𝑦}G(R T):={(y,x):x R y}.

对集合 𝑋 X 和集合 𝑌 Y 上的二元关系 𝑅 R 以及集合 𝑌 Y 和集合 𝑍 Z 上的二元关系 𝑆 S，我们可以定义其复合 𝑆 ∘𝑅 S∘R 满足 𝐺(𝑆 ∘𝑅) :={(𝑥,𝑧) :(∃ 𝑦 ∈𝑌) 𝑥 𝑅 𝑦 ∧𝑦 𝑆 𝑧}G(S∘R):={(x,z):(∃ y∈Y) x R y∧y S z}.

### 偏序集

定义

若集合 𝑆 S 上的一个二元关系 ⪯⪯ 具有 自反性、反对称性、传递性，则称 𝑆 S 是 偏序集（partially ordered set，poset），⪯⪯ 为其上一 偏序（partial order）．

若偏序 ⪯⪯ 还具有 连接性，则称其为 全序（total order），对应的集合称为 全序集（totally ordered set）、线性序集（linearly ordered set，loset）、简单序集（simply ordered set）．

不难发现 𝐍 N，𝐙 Z，𝐐 Q、𝐑 R 均关于 ≤≤ 构成全序集．

### 偏序集的可视化表示：Hasse 图

对于有限偏序集，我们可以用 Hasse 图直观地表示其上的偏序关系．

定义

对有限偏序集 𝑆 S 和其上的偏序 ⪯⪯，定义 𝑥 ≺𝑦 ⟺ (𝑥 ⪯𝑦 ∧𝑥 ≠𝑦)x≺y⟺(x⪯y∧x≠y) 其对应的 Hasse 图 为满足如下条件的图 𝐺 =⟨𝑉,𝐸⟩G=⟨V,E⟩：

- 𝑉 =𝑆 V=S,
- 𝐸 ={(𝑥,𝑦) ∈𝑆 ×𝑆 :𝑥 ≺𝑦 ∧((∄ 𝑧 ∈𝑆) 𝑥 ≺𝑧 ≺𝑦)}E={(x,y)∈S×S:x≺y∧((∄ z∈S) x≺z≺y)}

如对于集合 {0,1,2}{0,1,2} 的幂集 𝑆 S 和集合的包含关系 ⊆⊆，其对应的 Hasse 图为：

由于偏序具有反对称性，所以 Hasse 图一定是 有向无环图，进而我们可以根据 拓扑排序 对任意有限偏序集构造全序．

### 链与反链

定义

对偏序集 𝑆 S 和其上的偏序 ⪯⪯，称 𝑆 S 的全序子集为 链（chain）．若 𝑆 S 的子集 𝑇 T 中任意两个不同元素均不可比（即 (∀ 𝑎,𝑏 ∈𝑇) 𝑎 ≠𝑏 ⟹ (𝑎 ⋠𝑏 ∧𝑏 ⋠𝑎)(∀ a,b∈T) a≠b⟹(a⋠b∧b⋠a)），则称 𝑇 T 为 反链（antichain）．

对偏序集 𝑆 S 和其上的偏序 ⪯⪯，我们将偏序集 𝑆 S 的最长反链长度称为 宽度（partial order width）．

如对于集合 {0,1,2}{0,1,2} 的幂集 𝑆 S 和集合的包含关系 ⊆⊆，{∅,{1},{1,2}}{∅,{1},{1,2}} 为一条链，{{1},{0,2}}{{1},{0,2}} 为一条反链，𝑆 S 的宽度为 3 3.

### 预序集中的特殊元素

在预序集中，我们可以定义极大（小）元、上（下）界、上（下）确界等概念，这些概念可以推广到其他序关系中．

定义

对预序集 𝑆 S 和其上的预序 ⪯⪯，取 𝑆 S 中的元素 𝑚 m：

1. 若 (∀ 𝑎 ∈𝑆 ∖{𝑚}) ¬(𝑚 ⪯𝑎)(∀ a∈S∖{m}) ¬(m⪯a)，则称 𝑚 m 为 极大元（maximal element），
2. 若对 𝑇 ⊆𝑆 T⊆S 满足 (∀ 𝑡 ∈𝑇) 𝑡 ⪯𝑚(∀ t∈T) t⪯m，则称 𝑚 m 为 𝑇 T 的 上界（upper bound），
3. 若对 𝑇 ⊆𝑆 T⊆S 满足 𝑚 m 是 𝑇 T 的上界且对 𝑇 T 的任意上界 𝑛 n 均有 𝑚 ⪯𝑛 m⪯n，则称 𝑚 m 为 𝑇 T 的 上确界（supremum）．

类似可定义 极小元（minimal element）、下界（lower bound）和 下确界（infimum）．

如 1 1 是 𝐍+N+ 的极小元和下界．

可以证明：

- 预序集中，极大（小）元、上（下）界、上（下）确界都是不一定存在的，即使存在也不一定唯一．

- 若偏序集 𝑆 S 的子集 𝑇 T 存在上（下）确界，则一定唯一．

  我们可将 𝑇 T 的上确界、下确界分别记为 s u p 𝑇 sup T，i n f 𝑇 inf T. 若偏序集 𝑆 S 既有上界又有下界，则称 𝑆 S 是有界的．

在无限偏序集中，极大元不一定存在．可用 Zorn 引理（Zorn's Lemma）来判断无限偏序集中是否存在极大元．

Zorn 引理

Zorn 引理 也被称为 Kuratowski–Zorn 引理，其内容为：若非空偏序集的每条链都有上界，则该偏序集存在极大元．

Zorn 引理与 选择公理、良序定理 等价．

### 有向集与格

我们知道若偏序集的子集存在上（下）确界，则一定唯一．但是这一点并不适用于极大（小）元．例如：考虑偏序集 𝑆 ={{0},{1},{2},{0,1},{0,2},{1,2}}S={{0},{1},{2},{0,1},{0,2},{1,2}} 和其上的偏序 ⊆⊆，不难发现其有 3 3 个极大元和 3 3 个极小元．

我们希望通过向偏序集添加一定的条件来使得若极大（小）元存在则一定唯一，这样我们就可以定义最大（小）元的概念了．

有向集

对预序集 𝑆 S 和其上的预序 ⪯⪯，若 (∀ 𝑎,𝑏 ∈𝑆) (∃ 𝑐 ∈𝑆) 𝑎 ⪯𝑐 ∧𝑏 ⪯𝑐(∀ a,b∈S) (∃ c∈S) a⪯c∧b⪯c，则称 ⪯⪯ 为 𝑆 S 的一个 方向（direction），𝑆 S 称为 有向集（directed set）或 过滤集（filtered set）．

有时也将满足上述定义的集合 𝑆 S 称为 上有向集（upward directed set），类似地可定义 下有向集（downward directed set）．

有向集也可用如下方式定义：

有向集的等价定义

对预序集 𝑆 S 和其上的预序 ⪯⪯，若 𝑆 S 的任意有限子集 𝑇 T 均有上界，则称 ⪯⪯ 为 𝑆 S 的一个方向，𝑆 S 称为有向集．

不难发现：

- 若上有向集存在极大元，则一定唯一．我们将上有向集的极大元称为 最大元（greatest element）．
- 若下有向集存在极小元，则一定唯一．我们将下有向集的极小元称为 最小元（least element）．

有方向的偏序集中，对任意元素 𝑎,𝑏 a,b，{𝑎,𝑏}{a,b} 都有上界，若将上界修改为上确界，则得到了并半格的定义．

对偏序集 𝑆 S 和其上的偏序 ⪯⪯：

并半格

若对 𝑆 S 中的任意元素 𝑎,𝑏 a,b，{𝑎,𝑏}{a,b} 均有上确界 𝑐 c，则称 𝑆 S 为 并半格（join-semilattice，upper semilattice），并且我们称 𝑐 c 为 𝑎 a 和 𝑏 b 的 并（join），记为 𝑎 ∨𝑏 a∨b.

交半格

若对 𝑆 S 中的任意元素 𝑎,𝑏 a,b，{𝑎,𝑏}{a,b} 均有下确界 𝑐 c，则称 𝑆 S 为 交半格（meet-semilattice，lower semilattice），并且我们称 𝑐 c 为 𝑎 a 和 𝑏 b 的 交（meet），记为 𝑎 ∧𝑏 a∧b.

格

若 𝑆 S 既是并半格也是交半格，则称 𝑆 S 为 格（lattice）．

例如 6 0 60 的正因子构成的集合 𝑆 ={1,2,3,4,5,6,1 0,1 2,1 5,2 0,3 0,6 0}S={1,2,3,4,5,6,10,12,15,20,30,60} 关于整除构成偏序集，其上的任意正整数 𝑎,𝑏 a,b，l c m⁡(𝑎,𝑏)lcm⁡(a,b) 为 𝑎 a 和 𝑏 b 的并，g c d(𝑎,𝑏)gcd(a,b) 为 𝑎 a 和 𝑏 b 的交，从而 𝑆 S 是格．

### 对偶

在序理论中，对偶是非常常见的概念，如上文提到的极大元与极小元对偶、上界与下界对偶、上确界与下确界对偶．

对偏序集 𝑃 P 和其上的偏序 ⪯⪯，定义其 对偶（dual，opposite）偏序集 𝑃 𝑑 P d 满足：𝑥 ⪯𝑦 x⪯y 在 𝑃 P 中成立当且仅当 𝑦 ⪯𝑥 y⪯x 在 𝑃 𝑑 P d 中成立．将 𝑃 P 的 Hasse 图的边反转即可得到 𝑃 𝑑 P d 的 Hasse 图．

## Dilworth 定理与 Mirsky 定理

对有限偏序集 𝑆 S 和其上的偏序 ⪯⪯，我们有如下的一对对偶的定理：

Dilworth 定理

𝑆 S 的宽度（最长反链长度）等于最小的链覆盖数．

证明

考虑数学归纳法．当 |𝑆| ≤3|S|≤3 时，命题显然成立．

假设命题对所有元素个数小于 |𝑆||S| 的偏序集都成立，令 𝑆 S 的宽度为 𝑑 d. 若 |𝑆||S| 中所有元素均不可比，则命题显然成立，否则在 𝑆 S 中取一条长度大于 1 1 的链，令其中的最小元为 𝑚 m，最大元为 𝑀 M.

令 𝑇 =𝑆 ∖{𝑚,𝑀}T=S∖{m,M}，若 𝑇 T 中的宽度不超过 𝑑 −1 d−1，则由归纳假设知 𝑇 T 可被至多 𝑑 −1 d−1 条链覆盖，进而 𝑆 S 可被这些链再加上链 {𝑚,𝑀}{m,M} 覆盖，命题成立，否则说明 𝑇 T 中的宽度也为 𝑑 d，令 𝑇 T 中最长的一条反链为 𝐴 A.

我们考虑如下两个集合：

𝑆+:={𝑥∈𝑆:(∃ 𝑎∈𝐴) 𝑎⪯𝑥}S+:={x∈S:(∃ a∈A) a⪯x} 𝑆−:={𝑥∈𝑆:(∃ 𝑎∈𝐴) 𝑥⪯𝑎}S−:={x∈S:(∃ a∈A) x⪯a}

我们不难发现如下性质：

- 𝑆+ ∪𝑆− =𝑆 S+∪S−=S，
- 𝑆+ ∩𝑆− =𝐴 S+∩S−=A，
- |𝑆+| <|𝑆||S+|<|S|,|𝑆−| <|𝑆||S−|<|S|（因为 𝑚 ∉𝑆+m∉S+ 且 𝑀 ∉𝑆−M∉S−）．

对 𝑆+S+ 和 𝑆−S− 都应用归纳假设，则这两个集合的最小链覆盖数为 𝑑 d，且这些链中恰好包含一个 𝐴 A 中的元素 𝑎 a，设这些链分别为 𝐶+𝑎 C a+，𝐶−𝑎 C a−，则 {𝐶−𝑎 ∪{𝑎} ∪𝐶+𝑎}𝑎∈𝐴{C a−∪{a}∪C a+}a∈A 是 𝑆 S 的一个最小链覆盖，命题得证．

Mirsky 定理

𝑆 S 的最长链长度等于最小的反链覆盖数．

证明

设 𝑆 S 的最长链长度为 𝑑 d，则由定义，最小反链覆盖数至少为 𝑑 d.

令 𝑓(𝑠)f(s) 为以 𝑠 s 为最小元的最长链长度，注意到若 𝑓(𝑠) =𝑓(𝑡)f(s)=f(t)，则 𝑠 s 与 𝑡 t 不可比，进而 (∀ 𝑛 ∈𝐍) 𝑓−1({𝑛})(∀ n∈N) f−1({n}) 均为反链，其中 𝑓−1({𝑛}) :={𝑎 ∈𝑆 :𝑓(𝑎) =𝑛}f−1({n}):={a∈S:f(a)=n} 称为 水平集（level set）．

因此不难得出 {𝑓−1({𝑖}) :1 ≤𝑖 ≤𝑑}{f−1({i}):1≤i≤d} 是一个反链覆盖，从而最小反链覆盖数至多为 𝑑 d.

Dilworth 定理与 Hall 婚配定理 等价．

我们可以用 Dilworth 定理证明如下定理：

Erdős–Szekeres 定理

含至少 𝑟 𝑠 +1 r s+1 个元素的实数序列 {𝑎 𝑖}{a i} 要么有一个长为 𝑟 +1 r+1 的不下降子序列，要么有一个长为 𝑠 +1 s+1 的不上升子序列．

证明

设序列长度为 𝑛 ≥𝑟 𝑠 +1 n≥r s+1，定义偏序集 {(𝑖,𝑎 𝑖)}𝑛 𝑖=1{(i,a i)}i=1 n，其上的偏序 ⪯⪯ 定义为：

(𝑖,𝑎 𝑖)⪯(𝑗,𝑎 𝑗)⟺(𝑖≤𝑗∧𝑎 𝑖≤𝑎 𝑗)(i,a i)⪯(j,a j)⟺(i≤j∧a i≤a j)

假设该偏序集的宽度不超过 𝑠 s，则由 Dilworth 定理可知该偏序集可以被至多 𝑠 s 条链覆盖，若这些链的长度都不超过 𝑟 r，则序列所含元素数至多为 𝑟 𝑠 r s，与条件矛盾．

### 例题

Luogu P1020 [NOIP1999 提高组] 导弹拦截

某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统．但是这种导弹拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度．某天，雷达捕捉到敌国的导弹来袭．由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹．

输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少要配备多少套这种导弹拦截系统．

对于全部数据，满足导弹的高度为正整数，且不超过 5 ×1 0 4 5×10 4.

题解

令一共有 𝑛 n 个导弹，第 𝑖 i 个导弹的高度为 ℎ 𝑖 h i，则集合 {(𝑖,ℎ 𝑖)}𝑛 𝑖=1{(i,h i)}i=1 n 为偏序集，其上的偏序 ⪯⪯ 定义为：

(𝑖,ℎ 𝑖)⪯(𝑗,ℎ 𝑗)⟺(𝑖≤𝑗∧ℎ 𝑖≥ℎ 𝑗)(i,h i)⪯(j,h j)⟺(i≤j∧h i≥h j)

进而根据 Dilworth 定理有：序列的不上升子序列的最少覆盖数等于最长上升子序列长度．从而可以通过 最长不下降子序列的 𝑂(𝑛 l o g⁡𝑛)O(n log⁡n) 做法 解决本题．

参考代码

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    #include <algorithm>
    #include <iostream>
    #include <vector>
    using namespace std;

    int main() {
      vector<int> a;
      int x;
      while (cin >> x) a.push_back(x);
      vector<int> f, g;
      for (int i : a) {
        if (f.empty() || -i >= f.back())
          f.push_back(-i);
        else
          *upper_bound(f.begin(), f.end(), -i) = -i;
        if (g.empty() || i > g.back())
          g.push_back(i);
        else
          *lower_bound(g.begin(), g.end(), i) = i;
      }
      cout << f.size() << '\n' << g.size() << '\n';
      return 0;
    }

[TJOI2015] 组合数学

给一个 𝑛 n 行 𝑚 m 列的网格图，其中每个格子中均有若干块财宝．每次从左上角出发，只能往右或下走，每次经过一个格子至多只能捡走一块财宝．问至少要走几次才可能把财宝全捡完．

1 ≤𝑛 ≤1 0 0 0 1≤n≤1000，1 ≤𝑚 ≤1 0 0 0 1≤m≤1000，每个格子中的财宝不超过 1 0 6 10 6 块．

题解

不考虑网格图的点权，不难发现按给定的规则下在网格图上行走等价于在 DAG 上行走，从而我们可以将其视作 Hasse 图来构造偏序集，进而根据 Dilworth 定理有：DAG 的最小链覆盖数等于最大的点独立集大小．

因此本题所求即为给定网格图最大点权独立集的点权和．

令 𝑎 𝑖 𝑗 a i j 为网格图在点 (𝑖,𝑗)(i,j) 处的权值，𝑓(𝑖,𝑗)f(i,j) 为 从 (𝑖,𝑗)(i,j) 到 (1,𝑚)(1,m) 这个子网格中的答案，注意到每个点都和其右上角的点不相邻，则状态转移方程为：

𝑓(𝑖,𝑗)=m a x{𝑓(𝑖−1,𝑗),𝑓(𝑖,𝑗+1),𝑓(𝑖−1,𝑗+1)+𝑎 𝑖 𝑗}f(i,j)=max{f(i−1,j),f(i,j+1),f(i−1,j+1)+a i j}

答案即为 𝑓(𝑛,1)f(n,1).

参考代码

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    #include <algorithm>
    #include <cstdint>
    #include <iostream>
    #include <vector>
    using namespace std;

    int main() {
      int t = 0;
      cin >> t;
      while (t--) {
        int n, m;
        cin >> n >> m;
        vector<vector<int64_t>> a(n, vector<int64_t>(m));
        for (auto &i : a)
          for (auto &j : i) cin >> j;
        vector<vector<int64_t>> f(n, vector<int64_t>(m));
        for (int i = 0; i < n; ++i)
          for (int j = m - 1; j >= 0; --j)
            f[i][j] =
                max({(i == 0 ? 0 : f[i - 1][j]), (j == m - 1 ? 0 : f[i][j + 1]),
                     (i == 0 || j == m - 1 ? 0 : f[i - 1][j + 1]) + a[i][j]});
        cout << f[n - 1][0] << '\n';
      }
      return 0;
    }

### 习题

- [CTSC2008] 祭祀
- CodeForces 590E Birthday

## C++ 中的应用

另请参阅：排序相关 STL - 算法基础．

C++ STL 中 需要使用比较的算法和数据结构 中有序理论的应用．我们经常需要在 C++ 中自定义比较器，STL 要求 其必须为 严格弱序．令 << 为自定义比较器，则可以定义：

- 𝑥 >𝑦 x>y 为 𝑦 <𝑥 y<x；
- 𝑥 ≤𝑦 x≤y 为 𝑦 ≮𝑥 y≮x；
- 𝑥 ≥𝑦 x≥y 为 𝑥 ≮𝑦 x≮y；
- 𝑥 =𝑦 x=y 为 𝑥 ≮𝑦 ∧𝑦 ≮𝑥 x≮y∧y≮x.

## 参考资料与拓展阅读

1. Order theory - From Academic Kids
2. Binary Relation - Wikipedia
3. Order Theory - Wikipedia
4. Hasse diagram - Wikipedia
5. Directed set - Wikipedia
6. Order Theory, Lecture Notes by Mark Dean for Decision Theory
7. 卢开澄，卢华明，《组合数学》（第 3 版）, 2006
8. List of Order Theory Topics - Wikipedia
9. 浅谈邻项交换排序的应用以及需要注意的问题 by ouuan
10. One thing you should know about comparators—Strict Weak Ordering
11. Dilworth's theorem - Wikipedia
12. Dilworth's Theorem | Brilliant Math & Science Wiki
13. Hall's marriage theorem - Wikipedia
14. Hall's Marriage Theorem | Brilliant Math & Science Wiki
15. Dilworth 学习笔记 - Selfish

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Tiphereth-A, c-forrest, Enter-tainer, iamtwz, ImpleLee, isdanni, liuzimingc, opsiff, shaokeyibb, StudyingFather, Xeonacid
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用