AcWing 3510. 最长公共子序列
原题链接
中等
作者:
阴天快乐
,
2021-05-21 15:33:14
,
所有人可见
,
阅读 276
C++ 代码
/*
本题的关键是数组1中不存在重复的数字,因此如果数组2中存在相同的数字,
则数组2的数字在数组1中的位置一定是递增的
由此可以转换为求最长递增子序列的长度问题
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n;
int id[N],q[N];//q[i]表示长度为i的末尾的数字;
int dp[N];//dp[i],代表以 i 位位置上的值做为结尾的最长上升子序列的长度
int binary_search(int* arr,int n,int val){
int left=0,right=n;
while(left!=right){
int mid=left+(right-left)/2;
if(arr[mid]>=val){
right=mid;
}else{
left=mid+1;
}
}
return left;
}
int main()
{
scanf("%d", &n);
memset(id,-1,sizeof id);
for (int i = 0; i < n; i ++ ){
int x;
scanf("%d", &x);
id[x]=i;
}
q[0]=-1;
int ans=0;
memset(q,INT_MAX,sizeof q);
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
int k=id[x];
if(k==-1) continue;
dp[i]=binary_search(q,ans+1,k);//在长度为ans+1的q数组中,找到第一个比k大的数的位置。
q[dp[i]]=k;
ans=max(ans,dp[i]);
}
cout<<ans<<endl;
return 0;
}