NYOJ 79 攔截導彈：最長遞減子序列動態規劃解法

導彈攔截系統：最長嚴格遞減子序列（LDS）

經典動態規劃入門題。系統首發可達任意高度，後續每發高度必須**嚴格低於**前一發。求最大攔截數 = 最長嚴格遞減子序列長度。

問題建模

• 輸入：測試組數 N (≤10)，每組導彈數 m (≤20)，高度序列
• 輸出：每組最大攔截數
• 樣例：389 207 155 300 299 170 158 65 → 6（如 389,300,299,170,158,65）

動態規劃設計

狀態定義：b[i] 表示以第 i 個導彈結尾的最長遞減子序列長度

轉移方程：

b[i] = 1;  // 初始化
for (j = 1; j < i; j++)
    if (a[i] < a[j])          // 嚴格小於
        b[i] = max(b[i], b[j] + 1);

答案：max(b[1..m])

完整代碼

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
    int n, m, a[25], b[25];
    cin >> n;
    while (n--) {
        cin >> m;
        for (int i = 1; i <= m; i++) {
            cin >> a[i];
            b[i] = 1;
        }
        int ans = 0;
        for (int i = 2; i <= m; i++) {
            for (int j = 1; j < i; j++)
                if (a[i] < a[j])
                    b[i] = max(b[i], b[j] + 1);
            ans = max(ans, b[i]);
        }
        cout << ans << endl;
    }
    return 0;
}

關鍵避坑點

• 嚴格遞減：條件是 a[i] < a[j]，非 ≤，否則樣例會錯
• 數據範圍小（m≤20），O(n²) DP 完全足夠，無需 O(n log n) 優化
• 多測試用例循環讀取，注意數組重置

複雜度分析

• 時間：O(N × m²) ≤ 10 × 400 = 4000 次操作，極快
• 空間：O(m)