目录

Dilworth 定理 - NOIP1999T1

目录

题目是经典的导弹拦截。第一问很有信心的写下了最长非增序列。第二问就懵了。后来看了题解,有一个“Dilworth 定理”,现在将定理的表述和证明整理如下:

这是一个关于偏序集的定理。偏序集即偏序集合。

偏序的概念:设 $ \textbf{A} $ 是一个非空集合。 $ P $ 是 $ \textbf{A} $ 上的一个关系,若关系 $ P $ 是自反的、反对称的、传递的,则称 $ P $ 是集合 $ \textbf{A} $ 上的偏序关系。

即 $ P $ 满足下列条件:

  1. $ \forall a\in\textbf{A},\left ( a,a \right )\in P $ ;
  2. 若 $ \left ( a,b \right )\in P,\left ( b,a \right )\in P $ ,则 $ a=b $ ;
  3. 若 $ \left ( a,b \right )\in P,\left ( b,c \right )\in P $ ,则 $ \left ( a,c \right )\in P $ 。 我们用 $ a\leq b $ 表示 $ \left ( a,b \right )\in P $ 。

注:“ $ \leq $ ”只是符号,不代表不等关系。

例如, $ \left ( \textbf{A},\leq \right ) $ 是一个偏序集,我们定义 $ A=\left \{ 1,2,3 \right \} $ ,偏序 $ \leq $ 在 $ \textbf{A} $ 上表现为大于等于关系,则有: $ \leq =\left \{ \left \langle 3,3 \right \rangle,\left \langle 3,2 \right \rangle,\left \langle 3,1 \right \rangle\left \langle 2,2 \right \rangle,\left \langle 2,1 \right \rangle,\left \langle 1,1 \right \rangle \right \} $ 。

我们再来通过下面几个例子进一步了解偏序集:

  1. 实数集上的小于等于关系是一个偏序关系。
  2. 设 $ \textbf{S} $ 是集合, $ P\left(\textbf{A}\right) $ 是 $ \textbf{S} $ 的所有子集构成的集合,定义 $ P\left(\textbf{A}\right) $ 中两个元素 $ \textbf{A}\leq \textbf{B} $ 当且仅当 $ \textbf{A} $ 是 $ \textbf{B} $ 的子集,则 $ P\left(\textbf{A}\right) $ 在这个关系下成为偏序集。
  3. 设 $ \textbf{N} $ 是正整数集,定义 $ m\leq n $ 当且仅当 $ m $ 能整除 $ n $ ,不难验证这是一个偏序关系。

在偏序集中,有一个非常著名的定理,叫做“Dilworth 定理”。在介绍这个定理之前,我们需要介绍几个术语:

令 $ \left ( \textbf{A},\leq \right ) $ 是一个偏序集,对于集合中的两个元素 $ a,b $ ,如果有 $ a\leq b $ 或者 $ b\leq a $ ,则称 $ a $ 和 $ b $ 是可比的,否则 $ a $ 和 $ b $ 不可比。

: $ \left ( \textbf{A},\leq \right ) $ 是偏序集,其中 $ \textbf{A}=\left \{ 1,2,3,4,5 \right \} $ ,其中 $ \leq $ 是整除关系,那么对任意的 $ x\in P $ 都有 $ 1\leq x $ ,所以 $ 1 $ 和 $ 1,2,3,4,5 $ 都是可比的,但是 $ 2 $ 不能整除 $ 3 $ ,且 $ 3 $ 不能整除 $ 2 $ ,所以 $ 2 $ 和 $ 3 $ 是不可比的。

在X中,对于元素 $ a $ ,如果任意元素 $ b $ ,由 $ b\leq a $ 得出 $ b=a $ ,则称 $ a $ 为极小元。

一个反链 $ \textbf{A} $ 是 $ \textbf{X} $ 的一个子集,它的任意两个元素都不能进行比较。 一个链 $ \textbf{C} $ 是 $ \textbf{X} $ 的一个子集,它的任意两个元素都可比。

定理1:令 $ \left ( \textbf{A},\leq \right ) $ 是一个有限偏序集,并令 $ r $ 是其最大链的大小。则 $ \textbf{X} $ 可以被划分成 $ r $ 个但不能再少的反链。

定理2(Dilworth 定理):令 $ \left ( \textbf{A},\leq \right ) $ 是一个有限偏序集,并令 $ m $ 是反链的最大的大小。则 $ \textbf{X} $ 可以被划分成 $ m $ 个但不能再少的链。

证明:这里只对定理1进行证明,定理2的证明留给读者自行证明。 设 $ p $ 为最少反链个数;

  1. 先证明 $ \textbf{X} $ 不能划分成小于 $ r $ 个反链。由于 $ r $ 是最大链 $ \textbf{C} $ 的大小, $ \textbf{C} $ 中任两个元素都可比,因此 $ \textbf{C} $ 中任两个元素都不能属于同一反链。所以 $ p\geq r $ 。
  2. 设 $ \mathbf{X_{1}}=\mathbf{X} $ , $ \mathbf{A_{1}} $ 是 $ \mathbf{X_{1}} $ 中的极小元的集合。从 $ \mathbf{X_{1}} $ 中删除 $ \mathbf{A_{1}} $ 得到 $ \mathbf{X_{2}} $ 。注意到对于 $ \mathbf{X_{2}} $ 中任意元素 $ a_{2} $ ,必存在 $ \mathbf{X_{1}} $ 中的元素 $ a_{2} $ ,使得 $ a_{1}\leq a_{1} $ 。令 $ \mathbf{A_{2}} $ 是 $ \mathbf{X_{2}} $ 中极小元的集合,从 $ \mathbf{X_{2}} $ 中删除 $ \mathbf{A_{2}} $ 得到 $ \mathbf{X_{3}} $ ……最终,会有一个 $ \mathbf{X_{k}} $ 非空而 $ \mathbf{X_{k+1}} $ 为空。于是 $ \mathbf{A_{1}},\mathbf{A_{2}},\cdots ,\mathbf{A_{k}} $ 就是 $ \mathbf{x} $ 的反链的划分,同时存在链 $ a_{1}\leq a_{2}\leq\cdots\leq a_{k} $ ,其中 $ a_{i} $ 在 $ \mathbf{A_{i}} $ 内。由于 $ r $ 是最长链大小,因此 $ r\geq k $ 。由于 $ \mathbf{x} $ 被划分成了 $ k $ 个反链,因此 $ r=k\geq p $ 。因此 $ r=p $ ,得证。

那么这道题目就化简为求一遍最长非增序列和最长上升序列,DP 即可。

 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
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <vector>

using namespace std;

const int MAX = 128;

int N, f1[MAX], f2[MAX], ans1, ans2;
vector<int> pVec;

int main()
{
    cin >> N;
    int nTmp;
    for(int i = 0; i < N; i++)
    {
        cin >> nTmp;
        pVec.push_back(nTmp);
    }
    for(int i = 0; i < pVec.size(); i++)
    { f1[i] = f2[i] = 1; }
    for(int i = 1; i < pVec.size(); i++)
    {
        for(int j = 0; j < i; j++)
        {
            if(pVec[j] >= pVec[i] && f1[j] + 1 > f1[i])
            { f1[i] = f1[j] + 1; }
            if(pVec[j] < pVec[i] && f2[j] + 1 > f2[i])
            { f2[i] = f2[j] + 1; }
        }
    }
    ans1 = 0; ans2 = 0;
    for(int i = 0; i < pVec.size(); i++)
    {
        if(f1[i] > ans1) { ans1 = f1[i]; }
        if(f2[i] > ans2) { ans2 = f2[i]; }
    }
    cout << ans1 << " " << ans2 << endl;
    return 0;
}