学步园

题目大意是求下面两行数组的最长公共子序，但要注意数据范围：250＊250，暗示了题目复杂度必须在o(n^2)一下。

一般的dp求LCS复杂度为o(n^2)，所以不能用。但很容易想到，两者的LCS包含的元素一定是两者都有的元素，于是可以预处理一下数组，使之不包含两者不公有的元素，而剩下的元素次序不改变。

然后就该着眼于优化。不妨参考一下求加强版最长单调子序列（HOJ
10027 Longest Ordered Subsequence Extention）时，用了一个len数组记录同样长度下处于该位置的最小元素，然后查找时，二分处理，使o(n^2)的复杂度降为了o(nlogn)。

可以这样做，如样例中的第一行数组“1 7 5 4 8 3 9”，经过预处理后变为“1 5 4 8 3 9”，按照里面个元素出现的早晚/位置先后赋权重，使得“1” < “5” < “4” < “8” < “3” < “9”；这样第一列预处理后的数组成了天然的“单增”序列（题目指明不含相同元素）。

根据每个元素的权重，找出第二行数组的最长“单增”子序，即为二者的LCS。

AC代码：

#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>

using namespace std;

int T, t, n, p, q;
int i, j, k;
int len;
int ans;
int b[62501], s[62501];
int tb[62501], ts[62501];
int va[62501];
int r[62501];
bool v1[62501], v2[62501];

int b_search(int x, int lt, int rt)
{
        while (lt <= rt)
        {
                int mid = (lt + rt) >> 1;
                if (va[r[mid]] < va[x] && va[r[mid+1]] > va[x])
                        return mid + 1;
                else if (va[r[mid]] > va[x])
                        rt = mid - 1;
                else
                        lt = mid + 1;
        }
        return 1;
}

void judge(bool *v, int *ta, int length)
{
        for (i = 1; i <= length; i++)
        {
                scanf("%d", &ta[i]);
                v[ta[i]] = true;
        }
        return ;
}

void wrt(int *ta, int *a, int length)
{
        for (i = 1, k = 1; i <= length; i++)
        {
                if (v1[ta[i]] && v2[ta[i]])
                {
                        a[k] = ta[i];
//                        printf("%d\n", a[k]);
                        k++;
                }
        }
//        printf("\n");
        return ;
}

int main()
{
        #ifdef BellWind
                freopen("B.in", "r", stdin);
        #endif // BellWind

        while (~scanf("%d", &T))
        {
                for (t = 1; t <= T; t++)
                {
                        memset(v1, 0, sizeof(v1));
                        memset(v2, 0, sizeof(v2));

                        scanf("%d%d%d", &n, &p, &q);
                        p++; q++;

                        judge(v1, tb, p);
                        judge(v2, ts, q);

                        wrt(tb, b, p);
                        wrt(ts, s, q);

                        len = --k;
//                        printf("len: %d\n", len);

//                        for (i = 1; i <= len; i++)
//                        {
//                                printf("~%d %d\n", b[i], s[i]);
//                        }
//                        printf("\n");

                        for (i = 1; i <= len; i++) //赋权重
                        {
                                va[b[i]] = i;
                        }

//                        for (i = 1; i <= len; i++)
//                        {
//                                printf("..%d ", va[s[i]]);
//                        }
//                        printf("\n\n");

                        r[1] = s[1];
                        ans = 1;

                        for (i = 2; i <= len; i++)
                        {
                                if (va[s[i]] > va[r[ans]])
                                {
                                        ans++;
                                        r[ans] = s[i];
//                                        printf("#%d\n", s[i]);
                                }
                                else if (va[s[i]] < va[r[1]])
                                {
                                        r[1] = s[i];
                                }
                                else
                                {
                                        int j = b_search(s[i], 1, ans);
                                        r[j] = s[i];
                                }
                        }
                        printf("Case %d: %d\n", t, ans);
                }
        }

        return 0;
}