10635 - Prince and Princess

描述：這個需要改用新的算法，要不然會逾時，從網上找到了一種解決方法： LCS的nlogn算法就是退化成LIS，LIS nlogn的算法，就是LCS的時間複雜度。這個我引用某集訓的論文，簡單的講講。設序列A，B。記序列A中各個元素在B中的位置(降序排列），然後按照A中的的位置依次求出A的最長上升子序列。 例如：例如：有A={a,b,a,c,x}，B={b,a,a,b,c,a}則有a={6,3,2},b={4,1},c={5};x=/;（注意降序排列） 然後按A中次序排出{a(6,3,2),b(4,1),a(6,3,2),c(5),x()}={6,3,2,4,1,6,3,2,5}；對此序列求最長遞增子序列即可。 然後計算最長子序列就可以了
#include <cstdio>
#include <cstring>
int v[62510],arr[62510];
int main()
{
    //freopen("a.txt","r",stdin);
    int t=0,m,x,k;
    int n,p,q;
    scanf("%d",&m);
    while(m--)
    {
        scanf("%d%d%d",&n,&p,&q);
        p++;
        q++;
        memset(v,0,sizeof(int)*(n*n+1));
        k=0;
        for(int i=1; i<=p; i++)
        {
            scanf("%d",&x);
            v[x]=i;
        }
        for(int j=1; j<=q; j++)
        {
            scanf("%d",&x);
            if(v[x]) arr[k++]=v[x];
        }
        p=0;
        for(int i=0; i<k; i++)
        {
            if(!p) v[p++]=arr[i];
            else if(v[p-1]<arr[i]) v[p++]=arr[i];
            else
            {
                for(int j=p-1; j>=0; j--)
                    if(v[j]<arr[i])
                    {
                        v[j+1]=arr[i];
                        break;
                    }
                if(v[0]>arr[i]) v[0]=arr[i];
            }
        }
        printf("Case %d: %d\n",++t,p);
    }
    return 0;
}