Dilworth定理

$Dilworth$ 定理是组合数学的一个重要定理，它是定义在偏序集上的，在解决实际问题时非常有效。比如经典的题目“导弹拦截”。现在，我们就来对它一探究竟。

内容

偏序集上最小链划分中链的数量等于其反链长度的最大值。

Dilworth定理是定义在偏序集上的，什么是偏序集？我们定义一种比较关系，使得两种元素之间进行比较，例如对于元素为二元组 $(a,b),(c,d)$

我们定义 $(a,b)\le (c,d)$
当且仅当 $a\le c,b\le d$ ，那么这两个元素就可比了，但是如果 $a>c,b\le d$ ，那么这两个元素就不可比了。

偏序集可以允许不可比的元素存在，但是整个偏序集 $S$ 要满足一下几个性质：

如果对于每个 $a,b$ ，若 $a \le b$ ，我们连一条 $a−>b$ 的边，那么显然，整个偏序集构成一个 $DAG$ 。

我们现在来理解一下 $Dilworth$ 定理的内容，什么叫最小链划分？

我们将 $S$ 中的所有元素划分成若干条链，使每个元素都在且仅在唯一一条链中，叫链划分。

链，什么是链？

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

换句话说，你可以看成是 $DAG$ 上某条路径上的元素。

反链，那么，什么是反链？

正如名字一样，反链和链的定义恰好相反，对于一个集合，它是反链当且仅当这个集合里的元素两两都是不可比的。换句话说，这个集合里的任何两个元素无法联通。大家可以脑补一下。

结论
那么，了解了这两个知识以后，这个定理的内容就很清晰了，也就是说，我们将一个偏序集S
划分为若干个小集合，使得每个小集合里的元素构成一条链，这个最小的划分数量，等于这个偏序集最长的反链的长度。

这个很有用，可以把一些看起来很不可做的题目转化为十分简单的题目。

看起来很不好做，对吧？

我们定义这样一个偏序，其实是定义一个 $DAG$ ，对于每个点 $(i,j)$
，我们把它拆成 $val_{i,j}$ 个点。

这样就构成了一个新的点集。

然后对于新点集中每个点，向它所能到达的所有的点连一条有向边，这样，就构成了一个 $DAG$ ，那么，每一条路径，就是一条链，题目所求即这个 $DAG$ 的最小链划分，由 $Dilworth$ 定理，这个就等于 $DAG$
的最长反链的长度。

回到题目所给的模型，什么是这个 $DAG$ 的反链？

换句话说，就是网格图中两两不能到达的点。对于每个点，它右上角和左下角的矩形中的点都是两两无法到达的，我们就是要找到一条路径，选的点从右上到左下，使点权的和最大（因为这个时候，每个点所拆成的点都两两不可到达，所以直接全部加上就好了）。这个，就直接 $DP$ 了。

浅谈Dilworth定理

__END__