UVA 10635 Prince and Princess 最长公共子序列(nlongn)

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int INF = 999999999;

int a[62505];
int s[62505];
int dp[62505];

int main () {
    int T;
    cin >> T;
    for (int i_case = 1; i_case <= T; i_case++) {
        int n, _a, _b;
        cin >> n >> _a >> _b;

        memset(a, -1, sizeof a);
        for (int j=0; j<=_a; j++) {
            int tmp;
            scanf("%d", &tmp);    
            a[tmp] = j;
        }

        for (int i=0; i<=_b; i++) {
            int tmp;
            scanf("%d", &tmp);
            s[i] = a[tmp];
        }

        int k=0;
        for (int i=0; i<=_b; i++) {
            if (s[i] == -1) continue;
            s[k++] = s[i];
        }

        fill (dp, dp + k, INF);
        for (int i=0; i < k; i++) {
            *lower_bound(dp, dp+k, s[i]) = s[i];
        }
        printf("Case %d: %d\n", i_case, (int )(lower_bound(dp, dp+k, INF) - dp));
    }

    return 0;
}