HDU 4513 完美隊形 II：Manacher 算法加強版（非遞減回文）

題目大意

給定 n 人身高序列 h[1..n]，選取連續子段重新排列（保持相對順序）形成「完美隊形」：

1. 左右對稱（回文）；
2. 從左到中間高度非遞減（H[1] ≤ H[2] ≤ ... ≤ H[mid]）。
3. 求最大滿足條件的子段長度。

核心洞察

條件 2 意味著回文的左半部分單調非遞減，右半部分自動單調非增。這是在標準最長回文基礎上增加的單調性約束。

Manacher 算法改造

標準 Manacher 在擴展回文半徑時判斷 s[i-p[i]] == s[i+p[i]]。本題需額外檢查新加入的左端字符 ≤ 原左端字符（即向中心方向非遞減）。

預處理：插入特殊字符（如 0）使所有回文長度變奇數，原數組映射到偶數下標。

關鍵判斷邏輯

while (s[i - p[i]] == s[i + p[i]] 
       && s[i - p[i]] <= s[i - p[i] + 2])  // 新左端 ≤ 原左端（向中心非遞減）
    p[i]++;

s[i - p[i] + 2] 為上一輪擴展時的左端字符（間隔一個特殊字符）。

完整 C++ 代碼

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100009;
int s[N*2], p[N*2];

int manacher(int len) {
    int mx = 0, id = 0, ans = 1;
    p[0] = 0;
    for (int i = 1; i < len; ++i) {
        if (i < mx) p[i] = min(mx - i, p[2*id - i]);
        else p[i] = 1;
        // 擴展：字符相等 且 向中心非遞減
        while (s[i - p[i]] == s[i + p[i]] 
               && s[i - p[i]] <= s[i - p[i] + 2])
            ++p[i];
        if (i + p[i] > mx) {
            mx = i + p[i];
            id = i;
        }
        ans = max(ans, p[i] - 1); // 扣除特殊字符
    }
    return ans;
}

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        s[0] = -1; // 哨兵
        for (int i = 1; i <= n; ++i) {
            s[2*i-1] = 0;      // 特殊字符
            scanf("%d", &s[2*i]); // 實際身高
        }
        s[2*n+1] = 0;
        printf("%d\n", manacher(2*n+2));
    }
    return 0;
}

複雜度

• 時間 O(n)：Manacher 線性擴展，單調性判斷 O(1)。
• 空間 O(n)：輔助數組。

易錯點提示

• 哨兵 s[0] = -1 防止下標越界。
• 特殊字符取 0 需確保身高 > 0（題目隱含），否則用負數或更大值。
• 答案 p[i]-1 扣除中心特殊字符，得到原數組長度。