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;
 }