90求解,第二个点WA了

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

九头蛇 @ 2018-11-05 13:28:21

#include <bits/stdc++.h>
#define inf 1000000007
using namespace std;
int read( ){
    int x=0,y=1;
    char c=getchar( );
    while(c>'9'||c<'0'){if(c=='-')y=-1;c=getchar( );}
    while(c>='0'&&c<='9') {x=x*10+c-'0';c=getchar( );}
    return x*y;
}
int n,x,num=0;
int a[100001],g[100001],d[100001],s[100001];
int main( ){
    n=read( );
    for(register int i=1;i<=n;i++) {scanf("%d",&x);a[x]=i;}
    for(register int i=0;i<n;i++) {scanf("%d",&x);s[num++]=a[x];}
    for(register int i=1;i<=num;i++) g[i]=inf;
    int ans=0;
    for(register int i=1;i<num;i++){
        int k=lower_bound(g+1,g+n+1,s[i])-g;
        d[i]=k;
        g[k]=s[i];
        ans=max(ans,d[i]);
    }
    printf("%d\n",ans);
    return 0;
}

by Shen_Linwood @ 2021-07-06 14:12:50

同求解…


by A_Đark_Horcrux @ 2021-11-13 21:14:45

@九头蛇 @shenlw 数组开大点(


|