一看就是lis,但是普通的lis是行不通的,而且这里要记录lis路径,可以使用nlogn的lis算法。

nlogn的lis算法可以看这里最长上升子序列nlogn

在nlogn的算法中得出标记最小结尾数的数组f后,从后面往前面扫一遍即可。


题目地址:http://acm.uestc.edu.cn/#/problem/show/251


代码:

StatusAccepted
Time29ms
Memory1800kB
Length1083
LangC++


#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
const int maxn=100005;
int data[maxn], len[maxn], f[maxn], ans[maxn];
int cas, n, cnt;
int low_bound(int x){
    int l=1, r=cnt, mid;
    while(l<r){
        mid=(l+r)/2;
        if(f[mid]>=x)r=mid;
        else l=mid+1;
    }
    return l;
}
void solve(){
    cnt=1;
    len[cnt]=1;
    f[cnt]=data[1];
    for(int i=2;i<=n;i++){
        if(data[i]>f[cnt]){
            f[++cnt]=data[i];
            len[i]=cnt;
        }
        else{
            int t=low_bound(data[i]);
            f[t]=data[i];
            len[i]=t;
        }
    }
    int now=cnt, last=maxn;
    for(int i=n;i>0;i--){
        if(len[i]==now&&data[i]<last){
            ans[now--]=last=data[i];
        }
    }
}
int main()
{
    scanf("%d", &cas);
    while(cas--){
        scanf("%d", &n);
        for(int i=1;i<=n;i++)scanf("%d", &data[i]);
        solve();
        printf("%d\n", cnt);
        for(int i=1;i<=cnt;i++){
            printf("%d", ans[i]);
            putchar(i==cnt?'\n':' ');
        }
    }
    return 0;
}