题目大意
有两个长度分别为p+1和q+1的序列，每个序列中的各个元素互不相同，且都是1~n^2之间的整数。两个序列的第一个元素均为1.求出A和B的最长公共子序列长度。
题解
这个是大白书上的例题，不过这题真的很好，很考验思维。因为p和q都是250^2=62500,如果用LCS的话时间复杂度是O(pq)，显然会超时。。。。不过这题的两个序列很特殊，就是没有重复的元素，这样可以把A中的元素重新编号为1~p+1。然后B根据A也重新编号，这样，新的A和B的LCS实际上就是新的B的LIS。LIS可以在O(nlogn)时间内解决~~~
代码：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
#define MAXN 255*255
int a[MAXN],g[MAXN];
int num[MAXN];
int main()
{
int n,p,q,T,cnt,t=0;
scanf("%d",&T);
while(T--)
{
memset(num,0,sizeof(num));
scanf("%d%d%d",&n,&p,&q);
cnt=0;
for(int i=1;i<=p+1;i++)
{
int x;
scanf("%d",&x);
num[x]=i;
}
for(int i=0;i<=q;i++)
{
int x;
scanf("%d",&x);
if(num[x])
a[cnt++]=num[x];
}
g[0]=a[0];
int len=0;
for(int i=1;i<cnt;i++)
if(a[i]>g[len])g[++len]=a[i];
else
{
int pos=lower_bound(g,g+len,a[i])-g;
g[pos]=a[i];
}
printf("Case %d: %d\n",++t,len+1);
}
return 0;
}