题目链接：

http://acm.hust.edu.cn/vjudge/problem/visitOriginUrl.action?id=19051

题意：

有两个长度分别为p+1和q+1的由1到n2之前的整数组成的序列，每个序列的元素各不相等，两个序列第一个元素均为1。求两个序列的最长公共子序列。

分析：

LCS的复杂度为O(p∗q)，这题p,q最大为250 * 250，必T无疑。

注意题目说的每个序列的元素各不相等，那么就能保证我们可以把序列A的元素用1到p+1重新进行赋值，把B中元素根据A的赋值找到对应的标号，用0表示没有出现过，那么问题就可以转化为LIS啦，时间复杂度O(nlogn)，可以过了。

有关LIS的内容这里有一个http://blog.csdn.net/yukizzz/article/details/50620631

代码：

/*************************************************************************

    > File Name: 10635.cpp

    > Author: jiangyuzhu

    > Mail: 834138558@qq.com

    > Created Time: Sat 18 Jun 2016 08:57:43 PM CST

 ************************************************************************/

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<queue>

#include<stack>

using namespace std;

#define sa(n) scanf("%d", &(n));

typedef pair<int, int>p;

const int maxn = 250 + 5, mod = 1e9 + 7, oo = 0x3f3f3f3f;

int a[maxn * maxn], b[maxn * maxn], nb[maxn * maxn];

int pos[maxn * maxn];

int dp[maxn * maxn];

int main (void)

{

    int t;sa(t);

    for(int kas = 1; kas <= t; kas++){

        int n, p, q;sa(n);sa(p);sa(q);

        memset(pos, 0, sizeof(pos));

        for(int i = 0; i <= p; i++){

            sa(a[i]);

            pos[a[i]] = i;

        }

        memset(nb, 0, sizeof(nb));

        for(int i = 0; i <= q; i++){

            sa(b[i]);

            nb[i] = pos[b[i]];

        }

        memset(dp, 0x3f, sizeof(dp));

        for(int i = 0; i <= q; i++){

            *lower_bound(dp, dp + q + 1, nb[i]) = nb[i];

        }

        int ans = lower_bound(dp, dp + q + 1, oo) - dp;

        printf("Case %d: %d\n", kas, ans);

    }

    return 0;

}