導彈攔截變體問題：交替高度條件下的最長子序列動態規劃解法

問題描述

給定一系列按距離從近到遠排列的導彈高度 h[0..n-1] (n ≤ 1000)。新型攔截系統規則：

• 選擇第一枚導彈攔截
• 第 2 枚必須比第 1 枚低且更遠
• 第 3 枚必須比第 2 枚高且更遠
• 以此類推：奇數位攔截導彈高度遞增，偶數位遞減

求一次發射最多可攔截多少枚導彈。輸入以 n=0 結束。

動態規劃模型

定義 dp[i] 為以第 i 枚導彈結尾的最長合法序列長度。根據序列長度奇偶性決定下一步比較方向：

• 若 dp[j] 為奇數，下一枚需 更高 (h[i] > h[j])
• 若 dp[j] 為偶數，下一枚需 更低 (h[i] < h[j])

狀態轉移方程：

dp[i] = max(dp[i], dp[j] + 1)  for all j < i satisfying:
    (dp[j] % 2 == 1 && h[i] > h[j]) || (dp[j] % 2 == 0 && h[i] < h[j])

完整 C 實現

#include <stdio.h>
#include <stdlib.h>

#define MAXN 1010
int h[MAXN], dp[MAXN];

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

複雜度分析

• 時間複雜度：O(n^2)，n ≤ 1000 時約 10⁶ 次操作，極易通過 1 秒時限
• 空間複雜度：O(n)

優化提示

若需進一步優化至 O(n log n)，可維護兩組單調棧/線段樹分別處理奇偶長度轉移，但對本題規模非必要。