AcWing 3510. 最长公共子序列
原题链接
中等
作者:
T先生
,
2024-08-04 21:17:23
,
所有人可见
,
阅读 2
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
const int N = 1e6+10;
int q[N],id[N];
int main(){
int n;
cin>>n;
memset(id,-1,sizeof id);
for(int i = 0;i<n;++i){
int x;
scanf("%d",&x);
id[x] = i;
}
int tt = 0;
q[0] = -1;
for(int i = 0;i<n;++i){
int x;
scanf("%d",&x);
int k = id[x];
if(k == -1) continue;
int l = 0,r = tt;
while(l<r){
int mid = l+r+1>>1;
if(q[mid]< k) l = mid;
else r = mid - 1;
}
q[r+1] = k;
tt = max(tt,r+1);
}
cout<<tt<<endl;
return 0;
}