这道题卡 cin
有个条件很重要,a序列中所有值都不相同,这样就能把最长公共子序列映射为最长公共子序列。
用一个数组来记录 b序列中每一个值在a序列中出现的位置,
单调递增的子序列 , 就是最长公共子序列。
a b c d e
a d c d e
1 4 3 4 5
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 1e6+10;
int n,x;
int id[N]; // i在数组a中第一次出现的位置
int dp[N]; // dp 最长上升子序列
int main()
{
scanf("%d",&n);
memset(id,-1,sizeof id);
for(int i = 0; i < n; i ++ ){
scanf("%d",&x);
id[x]=i;
}
dp[0] = -1;
int tt = 0;
for(int i = 1; i <= n; i ++ ){
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(dp[mid]<k)l = mid;
else r = mid-1;
}
dp[r+1] = k;
tt = max(tt , r+1);
}
printf("%d\n",tt);
return 0;
}