UVa 10635 + NlogN-LIS

【Problem Link】

Prince and Princess

【题意】

有两个长度分别为p+1和q+1的序列,每个序列中的各个元素互不相同,切都是1~n²之间的整数.两个序列的第一个元素都是1,求出A和B的最长公共子序列长度.

【题解】

本体是LCS问题,但规模达到了250²=62500,O(pq)的算法显然太慢.所以考虑把A重新按照下标编号,然后输入B的时候判断B中的整数在A中的位置,不存在则为0或者不记录.然后就转换为了求B得最长单增子序列LIS问题.然后用O(nlog(n))的解法解决.

【Source Code】

github: UVa 10635.cpp


#include<bits/stdc++.h>
using namespace std;
const int maxn=250*250+10;
const int INF=0x3f3f3f3f;
int S[maxn],g[maxn],d[maxn];///LIS所需
int num[maxn]; ///num[x]为整数x的编号,num[x]=0表示在A中未出现过
int main(){
    int T;
    scanf("%d",&T);
    for(int kase=1;kase<=T;++kase){
        int N,p,q,x;
        scanf("%d%d%d",&N,&p,&q);
        fill(num,num+maxn,0);
        for(int i=1;i<=p+1;++i){
            scanf("%d",&x);
            num[x]=i;
        }
        int n=0;
        for(int i=0;i<q+1;++i){
            scanf("%d",&x);
            if(num[x]) S[n++]=num[x];
        }

        ///O(nlog(n))求解S[0]到S[n-1]的LIS
        for(int i=1;i<=n;++i){
            g[i]=INF;
        }
        int ans=0;
        for(int i=0;i<n;++i){
            int k=lower_bound(g+1,g+n+1,S[i])-g;///在g[1]~g[n]中查找
            d[i]=k;///k是长度
            g[k]=S[i];///g数组记录长度为k的目前最末(最大)元素大小
            ans=max(ans,d[i]);
        }
        printf("Case %d: %d\n",kase,ans);
    }
    return 0;
}