HDOJ 4745 Two Rabbits 題解：環狀石頭上雙兔跳躍的區間動態規劃

題目大意

n 塊石頭排成環，權重 a_i。兩兔子分別順時針、逆時針跳躍，每回合各選一塊未踩過的石頭跳過去。要求任意時刻兩兔站立石頭權重相等。兔子不能跳過自己已踩過的石頭。求最大回合數。n ≤ 1000。

關鍵轉化

環拆為鏈，複製一倍得到長度 2n 數組。兩兔路徑分別為鏈上的兩個區間，長度均為回合數 L，且對應位置權重相等。即尋找長度 L 的區間 [i, i+L-1] 和逆序區間 [j, j-L+1] 使得 a[i+k] == a[j-k]。等價於在擴展數組中尋找最長「雙向匹配」子序列。

區間 DP

定義 dp[i][j] 為區間 [i, j] 內可達成的最大回合數。轉移：

• dp[i][j] = max(dp[i+1][j], dp[i][j-1])
• 若 a[i] == a[j]，dp[i][j] = max(dp[i][j], dp[i+1][j-1] + 2)

初始 dp[i][i] = 1。按區間長度遞增 DP。

答案提取

因環長 n，兩兔路徑總長度 ≤ n。枚舉長度為 n/2 或 n/2-1 的區間：

ans = 1;
for (i=0; i+n/2-1 < 2n; i++) ans = max(ans, dp[i][i+n/2-1]);
for (i=0; i+n/2-2 < 2n; i++) ans = max(ans, dp[i][i+n/2-2] + 1);

AC 代碼 (C++)

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2200;
int n, a[maxn], dp[maxn][maxn];
int main() {
    while (scanf("%d", &n), n) {
        for (int i=0;i