AcWing 3510. 最长公共子序列
原题链接
中等
作者:
术
,
2021-05-17 14:08:32
,
所有人可见
,
阅读 229
#include <iostream>
#include <string.h>
using namespace std;
const int N=1e6+5;
int n;
int a[N],b[N];
int c[N];
int q[N];
//转化为最长上升子序列,B’表示B中每一个元素,在A出现的位置
//求B中每个元素在A中下标的最长上升子序列
int main()
{
cin>>n;
memset(c,-1,sizeof c);
for(int i=0; i<n; i++)
{
cin>>a[i];
c[a[i]]=i;
}
for(int i=0; i<n; i++)
cin>>b[i];
int tt=0;
q[0]=-1;////当前所有长度是i的上升子序列里,末尾的最小值 必然单调递增
for(int i=0;i<n;i++){
int k=b[i];
if(c[k]==-1) continue;
int l=0,r=tt;//二分找小于x的最大值
while(l<r){
int mid=l+r+1>>1;
if(q[mid]<c[k]) l=mid;
else r=mid-1;
}
tt=max(tt,r+1);
q[r+1]=c[k];//更新J+1
}
cout<<tt;
//cout << "Hello world!" {<< endl;
return 0;
}