POJ 1631 Bridging Signals：LIS 二分優化求最大不相交信號數

POJ 1631 Bridging Signals：LIS 二分優化求最大不相交信號數

問題建模

兩功能塊各有 p 個端口（1..p 自上而下編號）。給定一個排列，第 i 個數表示左側第 i 個端口連接右側哪個端口。兩信號交叉當且僅當連線相交。求最大不相交信號數 = 最長遞增子序列（LIS）長度。

數據範圍與算法選擇

p < 40000，測試用例多。O(n²) DP 會 TLE，必須用 O(n log n) 二分法。

二分法核心邏輯

• c[len]：長度為 len 的遞增子序列的最小結尾值
• 遍歷序列，對每個 a[i]：
  – 若 a[i] > c[len]，延長序列：c[++len] = a[i]
  – 否則二分查找 c[1..len] 中 最後一個 < a[i] 的位置 pos，更新 c[pos+1] = a[i]
• 最終 len 即 LIS 長度

二分查找函數

int search(int len, int x) {
    int le = 0, ri = len, ans = 0, mid;
    while (le <= ri) {
        mid = (le + ri) >> 1;
        if (c[mid] < x) { ans = mid; le = mid + 1; }
        else ri = mid - 1;
    }
    return ans; // 返回 ≤ x 的最大位置
}

完整 AC 代碼

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define N 100005
int a[N], c[N], n;

int search(int len, int x) {
    int le = 0, ri = len, ans = 0, mid;
    while (le <= ri) {
        mid = (le + ri) >> 1;
        if (c[mid] < x) { ans = mid; le = mid + 1; }
        else ri = mid - 1;
    }
    return ans;
}

int main() {
    int t; scanf("%d", &t);
    while (t--) {
        scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        int len = 1; c[1] = a[1];
        for (int i = 2; i <= n; i++) {
            int j;
            if (a[i] > c[len]) j = len++;
            else j = search(len, a[i]);
            c[j + 1] = a[i];
        }
        printf("%d\n", len);
    }
    return 0;
}

Sample I/O

Input:
4
6
4 2 6 3 1 5
10
2 3 4 5 6 7 8 9 10 1
8
8 7 6 5 4 3 2 1
9
5 8 9 2 3 1 7 4 6

Output:
3
9
1
4