Dilworth定理及LIS问题

一、引子：

洛谷1020 导弹拦截&&1223 木棍加工

求不上升子序列的最小划分数；

二、定理：
Dilworth定理：对偏序集<A，≤>，设A中最长链的长度是n，则将A中元素分成不相交的反链，反链个数至少是n

也可以认为：偏序集中全序集最小个数等于最大反链的长度（元素个数）

偏序集：“≤”是集合A上的一个满足自反性，反对称性，传递性的一个二元关系，则<A,≤>就是一个偏序集

全序集：对于偏序集<A,≤>，任意a,b∈A,a≤b和b≤a中至少有一个成立

反链：对于偏序集中任两元素而言，均不可比

说了这么多，这道题中运用的意思是：
不上升子序列的最小划分数等于最长上升子序列长度

三、解题

所以上面的问题就可以用LIS解决（T2先将长度作为关键字排序即可）

可是我的LIS是这样的：

L[1]=1;
for(int i=2;i<=n;i++){
    L[i]=0;
    for(int j=1;j<i;j++)
        if(s[j]<s[i])
            L[i]=max(L[i],L[j]);
    L[i]++;
}

对没错，O(n²)dp;

怎么优化呢？

四、nlogn的LIS

可以注意到，对于一个数x，长度为len的上升子序列s能不能“容忍”它的关键是s末尾的元素和x的大小关系，如果x较大，那么就可以拼接起来

有了这个发现，就可以维护一个数组d，d[i]存储当前长度为i的上升子序列的末尾

对于一个数x，如果它比当前最长的子序列的末尾大，最长长度就会增加1；

反之，因为d是单调递增的，就去寻找第一个比x大的末尾并用x替换他，由贪心知这样做是正确的，而这步可用upper_bound实现

d[1]=a[1];
for(int i=2;i<=n;i++){
    if(a[i]>d[len])
        d[++len]=a[i];
    else{
        int pos=upper_bound(d+1,d+1+n,a[i])-d;
        d[pos]=a[i];
    }
}

附：upper_bound和lower_bound均是二分实现，前者是第一个大的，后者是第一个大于等于的，如果没有返回的值是越界的

Dilworth定理及LIS问题

原文：https://www.cnblogs.com/MLETNxtl/p/12236488.html