最长上升子序列模型

• 模板

O(nlogn)
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N=100010;
int n,len;
int a[N],q[N];

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;++i) scanf("%d",&a[i]);
    len=0;
    for(int i=1;i<=n;++i){
        int l=0,r=len;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(q[mid]>=a[i]) r=mid-1;
            else l=mid;
        }
        len=max(len,r+1);
        q[r+1]=a[i];
    }
    printf("%d",len);
    return 0;
}

• 怪盗基德的滑翔翼
  思路：以a[i]为起点分别正向和反向求以a[i]为结尾的最长上升子序列的长度 最大值即为答案

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

const int N=110;
int T,n;
int a[N],f[N];

int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d",&n);
        for(int i=1;i<=n;++i) scanf("%d",&a[i]);
        int res=0;
        for(int i=1;i<=n;++i){
            f[i]=1;
            //保证用已更新的去更新 
            for(int j=1;j<i;++j)
                if(a[i]>a[j])
                    f[i]=max(f[i],f[j]+1);
            res=max(res,f[i]);
        }       
        for(int i=n;i;--i){
            f[i]=1;
            for(int j=n;j>i;--j)
                if(a[i]>a[j])
                    f[i]=max(f[i],f[j]+1);
            res=max(res,f[i]);
        }
        printf("%d\n",res);
    }
    return 0;
}

• 拦截导弹
  第二问的关键在于如何说明g数组为单调上升的序列
  其中g[i]表示第i套系统所拦截的最后一枚导弹
  从前往后考虑每个数 确定更新方式：
  1.如果没有比当前数大的 直接长度+1
  2.如果有比当前数大的 找到最小的更新（如果去更新大的，则后面的数也可能用到这个比较大的数）
  有意思的就来了
  如果直接加数 必然能使g数组单增
  而如果用一个数x去更新a<b<c中的b 由于x<c x>a(b为小于或等于x的最小值)
  那么更新之后 必然有a<x<c 即序列的单调性保持不变
  综上所述 我们通过g数组的更新方式证明了g数组一定为单增序列
  那么可以用cnt维护系统的个数 每次更新二分查找即可

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;

const int N=1010;
int n,a[N],q[N],g[N];

int LIS(){
    int len=0;
    for(int i=n;i;--i){
        int l=0,r=len;
        while(l<r){
            int mid=(l+r+1)>>1;
            if(q[mid]<=a[i]) l=mid;
            else r=mid-1;
        }
        len=max(len,r+1);
        q[r+1]=a[i];
    }
    return len;
}

int work(){
    int cnt=0;
    for(int i=1;i<=n;++i){
        int l=0,r=cnt;
        while(l<r){
            int mid=(l+r)>>1;
            if(g[mid]>=a[i]) r=mid;
            else l=mid+1;
        }
        if(g[r]>=a[i]) g[r]=a[i];
        else g[++cnt]=a[i];
    }
    return cnt;
} 

int main(){
    int t;
    while(cin>>t) a[++n]=t;
    printf("%d\n%d",LIS(),work());
    
    return 0;
}