HDU 4745 Two Rabbits——最長回文子串

這道題實際上是求一個序列的最長回文子串的長度，

這道題的特殊性就在于已知的序列是一個環，我們可以用倍增法将他擴充為一個鍊，然後求這個鍊長度為n以内的最長回文子串（大可不用考慮長度為n，隻需求這個2*n序列的最長回文子串即可，因為求2*n序列解的過程實際上把前面所有解都求出來了，最後隻要循環掃一便找出需要的解就可以，具體參考代碼最後兩個循環）

因為題目要求不能再經過已經經過的點，是以把最長回文子串的長度作為解有漏洞，如1 2 1 4，他的n以内的最長回文子串是1 2 1，長度為3，實際長度應該為4，出現了錯誤。

關于這個錯誤我就不做解釋了，這個要自己了解一下，我解釋的不周到的話可能會影響大家的思考，這裡隻給出解決方案：

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>

using namespace std;

const int maxn = 2020;
int n, a[maxn], dp[maxn][maxn];

int main()
{
    while (cin >> n && n) {
        for (int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            a[i + n] = a[i];
        }
        memset(dp, 0, sizeof(dp));

        for (int i = 2 * n; i >= 1; i--) {
            for (int j = i + 1; j <= 2 * n; j++) {
                dp[i][i] = 1;
                if (a[i] == a[j]) dp[i][j] = dp[i + 1][j - 1] + 2;
                else dp[i][j] = max(dp[i + 1][j], dp[i][j - 1]);
            }
        }

        int ans = 0;
        for (int i = 1; i <= n; i++) {
            ans = max(ans, dp[i][i + n - 1]);
        }
        for (int i = 1; i <= n; i++) {
            ans = max(ans, dp[i][i + n - 2] + 1);
        }
        printf("%d\n", ans);
    }
}