uva 10635 - Prince and Princess LCS

  利用重新编号将LCS变成LIS，即将第一个重新编号成1-n，在第二个中找LIS

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
int order[63010];
int King[63010],lenp,lenk;
int n;

int g[63010];
int LIS(int n,int A[],int INF)
{
    int i;
    for(i=1;i<=n;i++)g[i]=INF;
    int ans=0;
    for(i=1;i<=n;i++)
    {
        if(A[i]==0)continue;
        int k=lower_bound(g+1,g+n+1,A[i])-g;
        g[k]=A[i];
        ans=max(ans,k);
    }
    return ans;
}

int main()
{
    int T,C=0;
    scanf("%d",&T);
    while(T--)
    {
        memset(order,0,sizeof(order));
        scanf("%d%d%d",&n,&lenp,&lenk);
        n*=n;
        int i,j;
        lenp++;lenk++;
        for(i=1;i<=lenp;i++)
        {
            scanf("%d",&j);
            order[j]=i;
        }
        for(i=1;i<=lenk;i++)
        {
            scanf("%d",&j);
            King[i]=order[j];
        }
        printf("Case %d: %d\n",++C,LIS(lenk,King,n+1));
    }
}