UVA10635--Prince and Princess

题目传送

题意：

求a序列和b序列的最长公共序列（LCS）。

思路：

显然不能用二维数组的方法来做，那样会超时。因为a和b的里面的元素不相同，我们可以用位置来表示a序列，里面的值是【1，2，3…,p+1】，而新的b序列表示的是旧b里面的元素在a序列里面的位置，放入新b中，保证新b序列里面的元素位置是a和b的公共位置。因为a里面的位置是上升的，所以只要在新b中找LIS，就是a和b的LCS。

代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
const int N=2e5+10,INF=1e9+10;
int num[N],d[N],g[N],s[N],t,n,p,q;
int main()          
{
	scanf("%d",&t);
	for(int kase=1;kase<=t;kase++)
	{
		scanf("%d%d%d",&n,&p,&q);
		memset(num,0,sizeof num);
		//memset(d,0,sizeof d);
		memset(s,0,sizeof s);
		int cnt=0,ans=0,x;
		for(int i=1;i<=p+1;i++)
		{
			
			scanf("%d",&x);
			num[x]=i;//每个元素赋值位置。
		}
		for(int i=1;i<=q+1;i++)
		{
	
			scanf("%d",&x);
			if(num[x])s[cnt++]=num[x];//如果x在a中出现，则将在a中的位置放进去
		}
		//对num[0,1,....cnt-1]进行LIS
		for(int i=1;i<=cnt;i++)g[i]=INF;
		for(int i=0;i<cnt;i++)
		{
			int k=lower_bound(g+1,g+1+cnt,s[i])-g;
			//d[i]=k;
			g[k]=s[i];
			ans=max(ans,k);
		}
		printf("Case %d: %d\n",kase,ans);
	}
	return 0;
 }