题目链接：
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1576
题目意思：
有两个数组，求两个数组的最长公共子序列长度。两个数组中数都在1~n*n范围内，且数组内没有任意两个数相同。
解题思路:
常见的LCS时间复杂度为o(n*n)肯定行不通，考虑题目的特殊性，数的范围1~n*n，且任意两个数都不相同。如果把第一个数组对应成1,2,3,4...p+1。把第二个数组也对应起来，实际上问题就转化为了求第二个数组的LIS（可以用o(nlgn)的算法求解。问题就得到了解决。
代码：
//#include<CSpreadSheet.h>
#include<iostream>
#include<cmath>
#include<cstdio>
#include<sstream>
#include<cstdlib>
#include<string>
#include<string.h>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<set>
#include<stack>
#include<list>
#include<queue>
#include<ctime>
#include<bitset>
#define eps 1e-6
#define INF 0x3f3f3f3f
#define PI acos(-1.0)
#define ll __int64
#define LL long long
#define lson l,m,(rt<<1)
#define rson m+1,r,(rt<<1)|1
#define M 1000000007
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
#define Maxn 65000
int ha[Maxn];
int a[Maxn],b[Maxn];
int main()
{
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
int t,n,p,q;
scanf("%d",&t);
for(int ca=1;ca<=t;ca++)
{
scanf("%d%d%d",&n,&p,&q);
memset(ha,-1,sizeof(ha));
for(int i=1;i<=p+1;i++)
{
int cur;
scanf("%d",&cur);
ha[cur]=i; //hash一下
}
for(int i=1;i<=q+1;i++)
{
int cur;
scanf("%d",&cur);
a[i]=ha[cur]; //对应起来
}
int tt=0;
for(int i=1;i<=q+1;i++)
{
if(a[i]==-1) //不公共，不考虑
continue;
if(!tt) //第一个
{
++tt;
b[tt]=a[i];
continue;
}
else if(a[i]>b[tt]) //个数肯定增加
{
b[++tt]=a[i];
continue;
}
int temp=lower_bound(b+1,b+tt+1,a[i])-b; //找到恰好大于它的位置
b[temp]=a[i]; //更新小
}
printf("Case %d: %d\n",ca,tt);
}
return 0;
}