题目链接
https://vjudge.net/problem/UVA-10635
题意
有两个长度分别为p+1和q+1的序列，每个序列的各个元素互不相同，且都是1~n^2之间的整数。两人序列的第一个元素均为1.求出A和B的最长公共子序列长度
分析
直接采用LCS模板去解的话，时间复杂度为O(pq).时间超限。
注意到每个序列的各个元素互不相同，我们可以将A序列的各个元素离散化为一个顺序序列。而求一个顺序序列A与另一个序列B的最长公共子序列就等于B的最长上升子序列。而LIS的算法模板的时间复杂度可以达到O（nlogn)级别。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3fusing namespace std;const int maxn=1e5+100;
int a[maxn],s[maxn];
int num[maxn];int LIS(int *A,int n)
{int ans=0;for(int i=0;i<=n;i++) s[i]=INF;for(int i=0;i<n;i++){int k=lower_bound(s,s+n,A[i])-s;ans=max(ans,k+1);s[k]=A[i];}return ans;
}int main()
{int T;scanf("%d",&T);for(int kase=1;kase<=T;kase++){memset(num,0,sizeof(num));int n,p,q;scanf("%d%d%d",&n,&p,&q);for(int i=1;i<=p+1;i++){int x;scanf("%d",&x);num[x]=i;}int m=0;for(int i=1;i<=q+1;i++){int x;scanf("%d",&x);if(num[x])a[m++]=num[x];}int ans=LIS(a,m);printf("Case %d: %d\n",kase,ans);}return 0;
}