Dilworth定理

优美的Dilworth定理

Dilworth是针对偏序集的组合数学的一个重要定理，可以解决导弹拦截等问题（不要问我为什么优美.jpg

内容

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

理解

我来描述一下：

首先，Dilworth定理谁定义在偏序集上的，那什么是偏序集？？？我们（呸，不是我们，是数学家）定义了一种比较关系，使得两种元素之间进行比较，例如对于元素为（a，b）（c，d）的二元组，我们定义（a，b）<= （c，d）当且仅当，a <= b,b <= d，则这两个元素可比，其他情况都不可比

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

• 自反性（好像在哪里听过(*≧ω≦)）：∀a∈S, a < = a
• 对称性：∀a,b∈S,若a<=b,则b>=a
• 传递性：若a<=b,b<=c,则a<=c

链

对于S中所有的元素，我们按规定的两个元素的比较方式，将所有元素连起来，就构成了一条条链，使得每个元素都在且仅在唯一一条链中，这就叫最小链划分

反链

什么是反链？？？

意如其名，反链和链正好相反，对于一个集合，它是反链当且仅当这个集合里两个元素都是不可比的，也就是说，这个集合的任何一个元素都无法像链一样联通

结论：

我们将一个偏序集划分成若干个小集合，使得每个小集合中元素构成一条链，这个最小的划分数量就等于这个偏序集最长的反链的长度

导弹拦截

第一问就是求最长下降子序列的长度

第二问就是求有几个下降子序列，这个时候就可以通过求最长上升子序列的长度即可

第一问求最长下降子序列就用dp来求

确定状态：

拦截第i个导弹时系统拦截的最大长度

状态转移方程

dp[i] = max{dp[j]+ 1},j < i

#include <cstdio>
#include <cstring>
#include <string>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <stdlib.h>
#include <sstream>
#include <map>
#include <set>
using  namespace std;
#define inf 0x3f3f3f3f
#define MAX 1000000 + 7
#define endl '\n'
#define mod 1e9+7;
typedef  long long ll ;
//不开longlong见祖宗！
//ios::sync_with_stdio(false);
//cin.tie(0); cout.tie(0);
inline int IntRead(){char ch = getchar();int s = 0, w = 1;while(ch < '0' || ch > '9'){if(ch == '-') w = -1;
        ch = getchar();}while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0';ch = getchar();}return s * w;}

int n, tr[MAX], dp[MAX], len,maxn, ans, dpp[MAX];

int main(){
    len = 0;
    ans = -1e9;
    maxn = -1e9;
    while (cin>>tr[++len]) {
        ;
    }
    for(int i = 1; i < len; ++i){
        dp[i] = 1;dpp[i] = 1;
        for(int j = 1; j < i; ++j){
            if(tr[i] <= tr[j]){
                dp[i] = max(dp[i], dp[j] + 1);
            }
            if(tr[i] >= tr[j]){
                dpp[i] = max(dpp[i], dpp[j] + 1);
            }
        }
        maxn = max(maxn, dp[i]);
        ans = max(ans, dpp[i]);
    }
    cout<<maxn<<endl<<ans<<endl;   
}