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);
    }
}