HDU 1257 最少攔截系統：貪心 + 多維 LIS 變體（堆疊模型）

問題等價

導彈高度序列，每套系統只能攔截**非遞增**高度序列。求覆蓋整個序列所需的**最少非遞增子序列數**。

由 Dilworth 定理：最少非遞增子序列數 = **最長嚴格遞增子序列 (LIS) 長度**。

貪心模擬（堆疊模型）

維護多個「攔截系統」的**最後攔截高度**（即棧頂）。對每個新導彈高度 h：
尋找**第一個**棧頂 ≥ h 的系統，將其棧頂更新為 h（貪心：盡量用高度最低但足夠的系統）。
若無此系統，新建一個系統。
系統數即為答案。
實現：棧頂數組保持**遞增**順序，二分查找下界 `lower_bound`，O(log K)。

代碼

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        vector tops; // 各系統最後高度，遞增
        for (int i = 0, h; i < n; ++i) {
            cin >> h;
            auto it = lower_bound(tops.begin(), tops.end(), h);
            if (it == tops.end()) tops.push_back(h);
            else *it = h;
        }
        cout << tops.size() << '\n';
    }
    return 0;
}

原始題解邏輯（從小到大枚舉系統）

題目給出的代碼從第一個系統開始線性掃描，因 N≤10000 且系統數較少，O(N×K) 也能通過。但二分優化至 O(N log K) 更優雅。

複雜度

O(N log K)，K 為答案（系統數），極快。