最长公共子序列

模板库

地址

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 100000+9;
int n;
int b[MAXN];
int num[MAXN];
int dp[MAXN];
void solve(){
    memset(dp,0x7f,sizeof(dp));
    for(int i=1;i<=n;i++){
        int loc=upper_bound(dp+1,dp+n+1,num[i])-dp;
        dp[loc]=num[i];
    }
    printf("%d\n",lower_bound(dp+1,dp+n+1,dp[0])-(dp+1));
}
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int x;scanf("%d",&x);
        b[x]=i;
    }
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        num[i]=b[x];
    }
    solve();
    return 0;
}