UVA 10635 Prince and Princess（LCS）

題目大意是求下面兩行數組的最長公共子序，但要注意資料範圍：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;
}