hdu 4745 Two Rabbits

   區間dp，關鍵是想模型。題目其實可以轉化為求環上的最長非連續回文串，可以用區間dp做。。可以先把串copy成兩個，然後再做線性的最長回文串，雖然比直接環上做時間慢一些，但是比較容易寫。。dp[j][k]表示 j 到 k 表示的最長回文串，注意，這個回文串表示的只有一半，需要加的時候加 2 來保證每個人都把走完一個環。。。然後最後在考慮一下兩個兔子在同一塊石頭的情況。。    

#include<algorithm>  
#include<iostream>  
#include<cstring>  
#include<cstdio>  
#include<cmath>  
#define LL long long  
#define CLR(a, b) memset(a, b, sizeof(a))  
  
using namespace std;  
  
const int N = 2222;  
  
int a[N], dp[N][N];  
  
int main()  
{  
    int n, i, j, ans, k;  
    while(scanf("%d", &n), n)  
    {  
        CLR(dp, 0);  
        for(i = 1; i <= n; i ++)  
        {  
            scanf("%d", &a[i]);  
            a[i + n] = a[i];  
            dp[i][i] = dp[i + n][i + n] = 1;  
        }  
        for(i = 2; i <= n; i ++)  
        {  
            for(j = 1; j + i - 1 < 2 * n; j ++)  
            {  
                k = i + j - 1;  
                if(a[j] == a[k]) dp[j][k] = max(dp[j][k], dp[j + 1][k - 1] + 2);  
                dp[j][k] = max(max(dp[j][k], dp[j + 1][k - 1]), max(dp[j + 1][k], dp[j][k - 1]));  
            }  
        }  
        ans = 0;  
        for(i = 1; i <= n; i ++) ans = max(ans, dp[i][i + n - 1]);  
        for(i = 1; i <= n; i ++) ans = max(ans, dp[i][i + n - 2] + 1);  
        printf("%d\n", ans);  
    }  
}