HDU 1257 最少攔截系統：最長非遞增子序列 (LIS 變體) + 貪心二分 O(n log n)

問題

導彈高度序列，每套系統首發任意高，後續只能攔截 ≤ 前一發高度的導彈。求最少系統數攔截所有導彈。等價於：將序列分解為最少條**非遞增**子序列。

Dilworth 定理 / 貪心構造

維護每套系統**最後攔截高度** (即各非遞增子序列的尾元素)。對新導彈高度 x：
- 找到**第一個尾元素 ≥ x** 的系統，用 x 更新該尾元素 (貪心：留給更大導彈機會)。
- 若不存在，新增一套系統。
系統尾元素數組始終**嚴格遞增** (證明略)，可用二分查找 O(log k)。

代碼實現

#include 
#include 
using namespace std;
const int MAXN = 30005;
int tail[MAXN]; // 系統尾元素，遞增
int k = 0;      // 系統數

int findAndUpdate(int x) {
    int l=0, r=k-1, pos=k;
    while (l<=r) {
        int mid=(l+r)>>1;
        if (tail[mid] >= x) { pos=mid; r=mid-1; }
        else l=mid+1;
    }
    if (pos==k) tail[k++] = x; // 新系統
    else tail[pos] = x;        // 更新現有
    return pos==k; // 是否新增
}

int main() {
    int n, x;
    while (~scanf("%d",&n)) {
        k=0;
        int ans=0;
        while (n--) {
            scanf("%d",&x);
            if (findAndUpdate(x)) ans++;
        }
        printf("%d\n",ans);
    }
    return 0;
}

關鍵點

• 尾元素數組 tail[] 保持**非嚴格遞增** (允許相等)，二分找第一個 ≥ x。
• 等價於求最長嚴格遞增子序列 (LIS) 長度 (Dilworth 定理)，但直接貪心更直觀。
• n≤30000，O(n log n) 極快。