dp求最少不增子序列的划分数（覆盖数） 等于 最长递增子序列的长度

dilworth定理：
最长链长度=最小反链覆盖数 （默认反链尽可能长 ）
最长反链长度=最小链覆盖数 （默认链尽可能长 ）

链指任意两个元素可比较
反链任意两个元素不可比较

解释：
离散数学中有一个知识点叫作二元关系，所谓二元关系通俗的理解就是某一个元素有两个键值，用以下的代码来简单的理解一下

struct node{
    int a,b;
}; 

bool operator<(node n1,node n2){
    return n1.a < n2.a  &&  n1.b < n2.b;
}

在以上例子中，只有一个对象的a,b均小于另一个对象，两者才可比。
那么在一个序列中，我们将一个元素的值记作a，所在的位置记作b。
那么当且仅当位置靠左的元素小于位置靠右的元素的时候，这两者才可比。
所以在这里一个最长的链，就是最长递增子序列
同理，当位置靠左的元素不小于位置靠右的元素时，满足n1.b<n2.b但是不满足n1.a<n2.a
两者不可比较，反链要求其中任意两个元素均不可比较，那么最长的反链就是最长不增子序列。
再运用dilworth定理，我们便可以得到，最小（少）不增子序列的覆盖数就等于最长递增子序列的长度

例题： P1020 导弹拦截
参考博客

STL中具有排序功能的容器是按照优先级升序的方式排列的，大部分默认数大优先级则大

如：upper_bound()有三种比较元素的方式：重载小于号、自定义cmp函数、使用自带的比较算子（不写比较算子，默认数大优先级则大）
例如：
lower_bound(a + 1, a + 1 + n, x, cmp); //自定义cmp函数
lower_bound(a + 1, a + 1 + n, x, greater <int> () ); //使用自带的比较算子
lower_bound(a + 1, a + 1 + n, x); //默认数大优先级则大
总结：
若定义了数小优先级大则 upper_bound()找第一个小于它的；lower_bound()找第一个小于等于它的。
以后用cmp定义了数小优先</int>

#include<bits/stdc++.h>
using namespace std;
#define low(x) x&(-x)
#define ll long long 
int const N=1e5+7;
int cnt,cnt2;
int a[N];
int t[N];  
int main(){
    while(cin >> a[++cnt]);
    cnt--;    //a[cnt]吃掉了EOF,所以cnt-- 
//t[i]：最长不降子序列长度为i时，最优的结尾元素
    for(int i=cnt;i>=1;i--){
        if(cnt2==0) t[++cnt2]=a[i];
        else if(a[i]>=t[cnt2]) t[++cnt2]=a[i];
        else{
            int p=upper_bound(t+1,t+cnt2+1,a[i])-t;  //考虑用哪个函数时，考虑边界，就明白了，如t[cnt2-1]仍然比a[i]小或等于，将t[cnt2]=a[i],后面可以接更多的元素，则变保证了最优的结尾元素，并且这里的t是最长不降子序列，所以允许有重复的
            t[p]=a[i];
        }
    }
    cout << cnt2 << endl;
    cnt2=0;
    memset(t,0,sizeof(t));
//t[i]：最长递增子序列长度为i时，最优的结尾元素
    for(int i=1;i<=cnt;++i){
        if(cnt2==0) t[++cnt2]=a[i];
        else if(a[i]>t[cnt2]) t[++cnt2]=a[i];
        else{
            int p=lower_bound(t+1,t+cnt2+1,a[i])-t;  //与上同理
            t[p]=a[i];
        }
    }
    cout << cnt2 << endl;
    return 0;
}