HDU - Revenge of Segment Tree - 第二長遞增子序列 (SLIS)

問題描述

給定長度 N (N ≤ 1000) 的序列，求第二長遞增子序列長度。定義：最長遞增子序列 (LIS) 長度為 L。若存在 ≥2 條不同的 LIS，則第二長 = L；否則第二長 = L-1。

算法：O(N²) DP 統計 LIS 數量

標準 LIS DP：

• len[i] = 以 a[i] 結尾的 LIS 長度。
• cnt[i] = 以 a[i] 結尾的 LIS 條數 (飽和到 2 即可，只需知 ≥2)。

轉移：

for i = 1..N:
    len[i] = cnt[i] = 1
    for j = 1..i-1:
        if a[j] < a[i]:
            if len[j] + 1 > len[i]:
                len[i] = len[j] + 1
                cnt[i] = cnt[j]
            else if len[j] + 1 == len[i]:
                cnt[i] = min(2, cnt[i] + cnt[j]) // 只需知 ≥2
L = max(len[i])
total = sum(cnt[i] for i where len[i]==L)
answer = (total >= 2) ? L : L-1

參考代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;

int a[MAXN], len[MAXN], cnt[MAXN];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
        for (int i = 1; i <= n; i++) len[i] = cnt[i] = 1;

        int L = 1;
        for (int i = 2; i <= n; i++) {
            for (int j = 1; j < i; j++) {
                if (a[j] < a[i]) {
                    if (len[j] + 1 > len[i]) {
                        len[i] = len[j] + 1;
                        cnt[i] = cnt[j];
                    } else if (len[j] + 1 == len[i]) {
                        cnt[i] = min(2, cnt[i] + cnt[j]); // 防溢出，只需≥2
                    }
                }
            }
            L = max(L, len[i]);
        }

        int total = 0;
        for (int i = 1; i <= n; i++)
            if (len[i] == L) total += cnt[i];

        printf("%d\n", total >= 2 ? L : L - 1);
    }
    return 0;
}

關鍵細節

• cnt[i] 飽和到 2：避免數量指數增長導致溢出，邏輯上只需區分 0, 1, ≥2。
• 不同 LIS 定義：下標序列不同即視為不同 (即使值相同)。
• N=1000 時 O(N²) = 1e6 運算，極快。
• 若需輸出具體 SLIS，需記錄前驅並回溯，本題只問長度。

擴展：O(N log N) LIS 計數

利用線段樹 / Fenwick Tree 維護 (長度, 數量) 對的最大值，可將 LIS 計數優化至 O(N log N)，但 N=1000 非必要。