算法1
(DP) $O(nlogn)$
对于序列:
a1,a2…an
b1,b2…bn
此题关键:当我们匹配到ai时,我们必须保证ai在b序列中的坐标比ai-1在b序列中的坐标的要大.(假设ai,ai-1包含在公共子序列)
这道题有个很特殊的条件即:a中的数不重复。
所以我们可以把ai在b序列中的坐标存到一个数组里面.对于公共子序列s,si在b中的下标一定大于si-1,所以,公共子序列的坐标是有单调性的,所以找一个最长单调上升序列即可.
由于数据范围较大,所以需要对朴素最长单调上升序列方法优化,具体看算法基础课.
注意:不能存b序列的数在a序列的下标,因为b是有重复的,并且无法去重,因为不知道要保留哪个.
时间复杂度
O(nlog^n)
C++ 代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N=1e6+10;
int n,s1[N],s2[N],s[N],len=1;
int f[N],st[N],loc[N];
int s3[N],cnt=1;
int q[N];
//预处理s2中的数在s1中的编号放到s3[]中
//在s3中求一遍最长递增序列
//f[i]: s2中第i个数在s1中的序列编号的最长递增长度
int main()
{
cin>>n;
for(int i=1;i<=n;i++) scanf("%d",&s1[i]);
for(int i=1;i<=n;i++) scanf("%d",&s2[i]);
//预处理s2中的数在s1中的编号放到s3[]中
for(int i=1;i<=n;i++) loc[s1[i]]=i;
for(int i=1;i<=n;i++) if(loc[s2[i]]) s3[cnt++]=loc[s2[i]];
cnt--;
//贪心求最长上升子序列具体看算法基础课
int len1 = 0;
for (int i=1; i<=cnt; i++ )
{
int l=0, r=len1;
while (l<r)
{
int mid=l+r+1>> 1;
if (q[mid]<s3[i]) l=mid;
else r=mid-1;
}
len1=max(len1, r + 1);
q[r+1]=s3[i];
}
printf("%d\n", len1);
return 0;
}