【题解】 UVa 10635【Prince and Princess】

分析

这题就是求一个LCS,但是$O(pq)$的算法肯定超时,因为每个序列元素各不相同,因此可以把$A$中元素重新编号为$1$~$p+1$,则$B$就编为$B$中元素在$A$中出现的位置,$0$表示未出现,例如$A=(1,7,5,4,8,3,9),B=(1,4,3,5,6,2,8,9)$,则重新编号后$A=(1,2,3,4,5,6,7),B=(1,4,6,3,0,0,5,7)$。
这样,新的$A$和$B$的LCS就是$B$的LIS。由于LIS可以在$O(n\log n)$解决,所以本题也可以在该复杂度内解决。

代码

#include<cstdio>
#include<cstring>
#include<algorithm>
using std::lower_bound;using std::max;
const int INF = 0x7fffffff;
const int MAXN = 250 * 250 + 6;
int S[MAXN],g[MAXN],d[MAXN];
int num[MAXN];//renumber,num[x] == 0 means x didn't exist in A

int main(){
    int T,id = 0;scanf("%d",&T);
    while(T--){
        int N,p,q,x;scanf("%d %d %d",&N,&p,&q);
        memset(num,0,sizeof(num));
        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] != 0) S[n++] = num[x];}
        //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;//search in g[1~n]
            d[i] = k;g[k] = S[i];
            ans = max(ans,d[i]);
        }
        printf("Case %d: %d\n",++id,ans);
    }

    return 0;
}