Uva 10635 - Prince and Princess 问题转化，元素互不相同（在自身序列中独特）的两个数列的LCS，LIS 难度: 2

#include <algorithm>
#include <cassert>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <tuple>
#define LOCAL_DEBUG
using namespace std;
typedef pair<int, int> MyPair;
const int MAXN = 250 * 250 + 1;
int b[MAXN];
int leftNum[MAXN];

int main() {
#ifdef LOCAL_DEBUG
    freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\input.txt", "r", stdin);
    //freopen("C:\\Users\\Iris\\source\\repos\\ACM\\ACM\\output.txt", "w", stdout);
#endif // LOCAL_DEBUG
    int T;
    scanf("%d", &T);
    for (int ti = 1; ti <= T; ti++) {
        int n, p, q;
        scanf("%d%d%d", &n, &p, &q);
        map<int, int> a2ind;
        for (int i = 0; i <= p; i++) {
            int tmp;
            scanf("%d", &tmp);
            a2ind[tmp] = i;
        }
        int blen = 0;
        for (int i = 0; i <= q; i++) {
            int tmp;
            scanf("%d", &tmp);
            if (a2ind.count(tmp) != 0) {
                b[blen++] = a2ind[tmp];
            }
        }
        int leftlen = 0;
        for (int i = 0; i < blen; i++) {
            int ind = lower_bound(leftNum, leftNum + leftlen, b[i]) - leftNum;
            leftNum[ind] = b[i];
            if (ind == leftlen)leftlen++;
        }
        printf("Case %d: %d\n", ti, leftlen);
    }

    return 0;
}