UVA 10635 Prince and Princess

UVA_10635

    这个题目显然用n^2的最长公共子序列的算法会超时，后来看了别人的解题报告发现，原来最长公共子序列可以转化成最长上升子序列的问题，然后用最长上升子序列的nlogn的算法求解。

    但这个方法要求任意一个字符在两序列中出现的频率都要比较低，因为转化成最长上升子序列的算法的最坏复杂度是n^2log(n^2)。而这个题目恰好每个数字最多只在两序列中各出现一次，所以就可以达到nlogn的复杂度了。

#include<stdio.h>
#include<string.h>
#define MAXD 70000
int N, P, Q, s[MAXD], r[MAXD];
void solve()
{
    int i, j, p, q, top, mid, max, min;
    scanf("%d%d%d", &N, &P, &Q);
    P ++, Q ++;
    memset(r, 0, sizeof(r));
    for(i = 1; i <= P; i ++)
    {
        scanf("%d", &p);
        r[p] = i;
    }
    s[0] = top = 0;
    for(i = 1; i <= Q; i ++)
    {
        scanf("%d", &p);
        q = r[p];
        if(!q)
            continue;
        if(q > s[top])
            s[++ top] = q;
        else
        {
            max = top;
            min = 0;
            for(;;)
            {
                mid = (max + min) / 2;
                if(mid == min)
                    break;
                if(s[mid] < q)
                    min = mid;
                else
                    max = mid;
            }
            s[mid + 1] = q;
        }
    }
    printf("%d\n", top);
}
int main()
{
    int t, tt;
    scanf("%d", &t);
    for(tt = 0; tt < t; tt ++)
    {
        printf("Case %d: ", tt + 1);
        solve();
    }
    return 0;
}