POJ 1836 Alignment：枚舉中間點雙向 LIS 解士兵排隊問題

題目大意

n ≤ 1000 名士兵按編號 1~n 排成一排，身高已知。讓部分士兵出列，使剩餘士兵（保持相對順序）滿足：每人向左或向右看，視線不被更高或等高者擋住。即序列呈「先嚴格遞增後嚴格遞減」的山脈形狀。求最少出列人數。

轉化模型

剩餘序列需存在分割點 k，使 h[1] < h[2] < ... < h[k] > h[k+1] > ... > h[m]。
枚舉分割點 i (1 ≤ i < n)，左邊求最長上升子序列 (LIS)，右邊求最長下降子序列 (LDS，即反序列 LIS)。
最大保留人數 = max_{i} (LIS[1..i] + LDS[i+1..n])。
答案 = n - 最大保留。

O(n log n) 雙向 LIS 實現

利用「耐心排序」維護 d[len]，可同時得到每個前綴的 LIS 長度與每個後綴的 LDS 長度。

C++ 代碼

#include 
using namespace std;
const int MAXN = 1005;
double h[MAXN];
int dp[MAXN], lis[MAXN], lds[MAXN];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    while (cin >> n) {
        for (int i = 1; i <= n; ++i) cin >> h[i];
        int ans = 0;
        // 枚舉分割點 i (左邊以 i 結尾，右邊以 i+1 開頭)
        for (int i = 1; i < n; ++i) {
            // 左側 1..i 的 LIS
            int len = 0;
            for (int j = 1; j <= i; ++j) {
                int pos = lower_bound(dp, dp+len, h[j]) - dp;
                dp[pos] = h[j];
                if (pos == len) ++len;
                lis[j] = pos + 1;
            }
            int maxLis = *max_element(lis+1, lis+i+1);
            // 右側 i+1..n 的 LDS（反序列 LIS）
            len = 0;
            for (int j = n; j > i; --j) {
                int pos = lower_bound(dp, dp+len, h[j]) - dp;
                dp[pos] = h[j];
                if (pos == len) ++len;
                lds[j] = pos + 1;
            }
            int maxLds = 0;
            for (int j = i+1; j <= n; ++j) maxLds = max(maxLds, lds[j]);
            ans = max(ans, maxLis + maxLds);
        }
        cout << n - ans << '\n';
    }
    return 0;
}

優化：一次遍歷得所有前綴/後綴 LIS

正向遍歷記錄 preLIS[i] = 以 i 結尾的 LIS 長度；反向遍歷記錄 sufLDS[i] = 以 i 開頭的 LDS 長度。然後枚舉分割點 i，取 max(preLIS[i]) + max(sufLDS[i+1])。複雜度降為 O(n log n) 總體。

總結

POJ 1836 是「雙向 LIS 組合」的典型應用。關鍵洞察：山脈序列 = 前綴 LIS + 後綴 LDS。枚舉分割點 + O(n log n) LIS 模板，輕鬆解決 n ≤ 1000 甚至 n ≤ 10⁵ 的擴展版本。