渡輪問題 - 最大不交叉航線數 (最長不下降子序列應用)

問題建模

河流南北兩岸各有 N 個城市 (N ≤ 1000)，北岸城市位置 C、南岸城市位置 D 形成友好城市對。需選擇最多城市對建立航線，使任兩航線不交叉。等價於：按北岸位置排序後，南岸位置序列的最長不下降子序列 (LNDS) 長度即為最大航線數。

算法步驟

1. 讀入 N 對 (C, D)。
2. 以 C 為關鍵字升序排序，若 C 相同則按 D 升序 (題目隱含 C 唯一)。
3. 對排序後的 D 序列求 LNDS 長度 (O(N²) DP 或 O(N log N) 貪心+二分)。

O(N²) DP 參考代碼

#include <stdio.h>

int a[1001], b[1001], dp[1001];

int main() {
    int len, width, n;
    scanf("%d %d %d", &len, &width, &n);
    for (int i = 1; i <= n; i++) scanf("%d %d", &a[i], &b[i]);

    // 按北岸位置 a 排序，同步調整 b
    for (int i = 1; i < n; i++)
        for (int j = 1; j <= n-i; j++)
            if (a[j] > a[j+1]) {
                int t = a[j]; a[j] = a[j+1]; a[j+1] = t;
                t = b[j]; b[j] = b[j+1]; b[j+1] = t;
            }

    int ans = 0;
    for (int i = 1; i <= n; i++) {
        dp[i] = 1;
        for (int j = 1; j < i; j++)
            if (b[j] <= b[i] && dp[j] + 1 > dp[i])
                dp[i] = dp[j] + 1;
        if (dp[i] > ans) ans = dp[i];
    }
    printf("%d\n", ans);
    return 0;
}

範例驗證

輸入：

30 4
7
22 4
2 6
10 3
15 12
9 8
17 17
4 2

輸出：4 (對應南岸位置序列 2, 3, 8, 12 或 4, 6, 8, 17 等)。

優化提示

N ≤ 1000 時 O(N²) 可接受；若 N 更大，可改用 tails 陣列 + 二分查找實現 O(N log N) LIS/LNDS。