O(nlogn)怎么T了??dalao求助!

P1439 【模板】最长公共子序列

Dark_Van @ 2019-02-01 21:07:11

T了2,8,9,10四个点

求助!

#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=100010;

int n,a[MAXN],b[MAXN];
int c[MAXN];
int stack[MAXN];
int ans=1;

int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=n;i++)
        scanf("%d",&b[i]);
    for(int i=1;i<=n;i++)
        for(int j=1;i<=n;j++)
            if(b[j]==a[i]){
                c[j]=i;
                break;
            }
    stack[1]=c[1];
    for(int i=2;i<=n;i++){
        if(stack[ans]<c[i]){
            stack[++ans]=c[i];
        }else{
            stack[lower_bound(stack+1,stack+ans+1,c[i])-stack]=c[i];
        }
    }
    printf("%d",ans);
    return 0;
}

by 什么叫中二呀 @ 2019-02-11 22:39:54

好吧好像只是因为我太弱了才不知道映射是个啥……


by Surpersolo @ 2019-08-19 10:36:26

@81季涛 你还是新手啊可以慢慢学的,不要急慢慢来

上一页 |