HDU 4745 Two Rabbits：環上最長回文子序列區間 DP

題目大意

環形排列 n 塊石頭（n ≤ 1000），每塊有權值 a[i]。兩隻兔子分別順時針、逆時針跳躍，每次跳躍落腳石頭權值必須相等。問一圈內最多能經過多少塊石頭（即最長非連續回文子序列長度）。

轉化為環上最長回文子序列

兔子跳躍序列對應一個回文子序列：左兔走過的石頭序列與右兔走過的序列相反且權值相等。環狀意味著序列首尾相連。

解法一：倍增鏈 + 滑動窗口

將環拆成鏈，倍增數組 a[1..2n]。對長度為 n 的滑動窗口，求區間最長回文子序列（LPS）。標準區間 DP：dp[i][j] = max(dp[i+1][j], dp[i][j-1], dp[i+1][j-1]+2 if a[i]==a[j])。但需注意：回文子序列兩端可以不取窗口端點，中間可留一個石頭作為起點（即窗口長度 n-1 的 LPS + 1）。答案為 max( 窗口 n 的 LPS, 窗口 n-1 的 LPS + 1 )。

解法二：直接切環 + 分治

不倍增，直接在環上 DP。將環在任意點切開成鏈，求 dp[1][i] + dp[i+1][n] 的最大值，其中 dp[l][r] 為區間 [l,r] 的 LPS。因為回文中心可作為起點，無需額外 +1。複雜度 O(n²)。

代碼（解法二，更簡潔）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int a[MAXN], dp[MAXN][MAXN];

int main() {
    int n;
    while (cin >> n, n) {
        for (int i = 1; i <= n; ++i) cin >> a[i];
        for (int i = 1; i <= n; ++i) dp[i][i] = 1;
        for (int len = 2; len <= n; ++len) {
            for (int i = 1; i+len-1 <= n; ++i) {
                int j = i+len-1;
                dp[i][j] = max(dp[i+1][j], dp[i][j-1]);
                if (a[i] == a[j]) dp[i][j] = max(dp[i][j], dp[i+1][j-1] + 2);
            }
        }
        int ans = 0;
        for (int i = 1; i <= n; ++i)
            ans = max(ans, dp[1][i] + dp[i+1][n]);
        cout << ans << '\n';
    }
    return 0;
}

總結

環狀問題常用倍增或枚舉切點轉化為鏈。回文子序列區間 DP 經典模板，注意邊界與合併邏輯。