学步园

题意：有两个长度分别为p+1和q+1的序列，每个序列中的元素互不相同，且都是1到n^2之间的整数（2<=n<=250），两个序列的第一个元素均为1。求A和B的最长公共子序列的长度。

思路：原本是LCS问题，但是普通的LCS算法复杂度是O(pq)显然TLE。注意到元素均不相同，可以把A中的元素重新编号为1到p+1。例如样例中的A={1,7,5,4,8,3,9}，B={1,4,3,5,6,2,8,9}，那么把A重新编号为{1,2,3,4,5,6,7}，则B={1,4,6,3,0,0,5,7}，其中0表示A中没有出现过（事实上可以直接删除这些元素，因为他们肯定不在LCS里面）。这时候，答案就是新的B的LIS，LIS的复杂度是O(nlogn)，因此可以解决问题。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define INF 0x3f3f3f3f
using namespace std;

int T;
int n,p,q;

const int maxn=255*255;
int F[maxn];
int b[maxn];
int g[maxn];
int dp[maxn];
int t;

int main()
{
	int ca=0;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&p,&q);
		
		memset(F,0,sizeof(F));
		for(int i=1;i<=p+1;++i)
		{
			scanf("%d",&t);
			F[t]=i;
		}
		
		int cntB=0;
		for(int i=1;i<=q+1;++i)
		{
			scanf("%d",&t);
			if(F[t]) b[cntB++]=F[t];
		}
		
		int ans=0;
		for(int i=1;i<=cntB;++i) g[i]=INF;
		for(int i =0;i<cntB;++i)
		{
			int k=lower_bound(g+1,g+cntB+1,b[i])-g;
			dp[i]=k;
			g[k]=b[i];
			ans=max(ans,dp[i]);
		}
		printf("Case %d: %d\n",++ca,ans);
	}
	return 0;
}