Uva 10635 皇子和公主（LCS转LIS+二分）

Uva 10635 王子和公主（LCS转LIS+二分）

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
int n,m,a[62505],b[62505],d[62505];
int binary(int left,int right,int key)
{	
	while(left<right)
	{
		int mid=(left+right)>>1;
		if(d[mid]>key) right=mid;
		else left=mid+1;
	}
	return right;
}
int main(int argc, char *argv[])
{
	int i,t,tt,ans,Case=0;
	cin>>t;
	while(t--)
	{   Case++;
		cin>>n>>n>>m;
		n++;m++;
		memset(a,0,sizeof(a));
		for(i=1;i<=n;i++)
		{
			scanf("%d",&tt);  a[tt]=i;
		}
		for(n=i=1;i<=m;i++)
		{
			scanf("%d",&tt);   if(a[tt]!=0) b[n++]=a[tt];
		}
		d[ans=1]=b[1];
		for(i=2;i<n;i++)
		{
			if(b[i]>d[ans]) d[++ans]=b[i];
			else
			{
				m=binary(1,ans,b[i]);
				d[m]=b[i];
			}
		}
		cout<<"Case "<<Case<<": "<<ans<<endl;
	}
	return 0;
}