UVA 10635 Prince and Princess：LIS 求最長公共子序列

題目背景

王子和公主在 n×n 方格中從 1 走到 n²，給出兩人的路徑序列，求兩條路徑的最長公共子序列（LCS）長度。n ≤ 250，序列長度最多 62500，傳統 O(n²) LCS 會超時，需用 O(n log n) 的 LIS 優化。

核心洞察：LCS 轉 LIS

若其中一條序列元素唯一（本題中王子路徑無重複），可將另一條序列中的元素映射為第一條序列中的位置索引，則 LCS 等價於映射後序列的最長遞增子序列（LIS）。

具體步驟：

1. 讀取王子路徑長度 p，記錄每個格子在王子路徑中的位置 prince[pos] = index。
2. 讀取公主路徑長度 q，建立映射 princess[grid] = index。
3. 將王子路徑轉換為公主路徑中的索引序列：a[i] = princess[prince[i]]。
4. 對序列 a 求 LIS 長度即為答案。

LIS O(n log n) 算法詳解

維護一個數組 d[len] 表示長度為 len 的遞增子序列的最小尾元素。遍歷序列每個元素 x：

• 若 x > d[len]，則 len++，d[len] = x。
• 否則二分查找最大的 j 使 d[j] < x，更新 d[j+1] = x。

最終 len 即為 LIS 長度。利用 d 數組單調遞增特性，二分查找將複雜度降至 O(n log n)。

完整代碼

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
const int MAXN = 250*250 + 10;

int n, p, q;
int prince[MAXN], princess[MAXN];
int d[MAXN];

int LIS(int len) {
    int lisLen = 0;
    memset(d, 0, sizeof(d));
    for (int i = 1; i <= len; i++) {
        int l = 1, r = lisLen;
        while (l <= r) {
            int mid = (l + r) >> 1;
            if (prince[i] > d[mid]) l = mid + 1;
            else r = mid - 1;
        }
        d[l] = prince[i];
        if (l > lisLen) lisLen = l;
    }
    return lisLen;
}

int main() {
    int T; scanf("%d", &T);
    for (int cas = 1; cas <= T; cas++) {
        scanf("%d%d%d", &n, &p, &q);
        memset(prince, 0, sizeof(prince));
        memset(princess, 0, sizeof(princess));
        for (int i = 1; i <= p; i++) scanf("%d", &prince[i]);
        for (int i = 1; i <= q; i++) {
            int x; scanf("%d", &x);
            princess[x] = i;
        }
        for (int i = 1; i <= p; i++)
            prince[i] = princess[prince[i]];
        printf("Case %d: %d\n", cas, LIS(p));
    }
    return 0;
}

複雜度分析

• 時間：O((p+q) + p log p) ≈ O(n² log n)，n=250 時極快。
• 空間：O(n²)。

總結

本題展示了將 LCS 轉化為 LIS 的經典技巧：利用其中一序列元素唯一的性質建立位置映射，再用 O(n log n) LIS 算法高效求解。這是處理長序列 LCS 問題的標準優化手法。