hdu - 4745 - Two Rabbits

題意：兩只兔子，在n塊圍成一個環形的石頭上跳躍，每塊石頭有一個權值ai，一只從左往右跳，一只從右往左跳，每跳一次，兩只兔子所在的石頭的權值都要相等，在一圈內（各自不能超過各自的起點，也不能再次回到起點）它們最多能經過多少個石頭(1 <= n <= 1000, 1 <= ai <= 1000)。   題目鏈接：http://acm.hdu.edu.cn/showproblem.php?pid=4745   ——>>模擬樣例後，初看挺像歐拉回路，接著同學說應是最長公共子序列LCS，接著就慘了，一直到比賽Ended都TLE……   原來，只是簡單的dp求最長回文子序列……   假設一個有11個數的序列：1 2 3 4 3 2 1        8 9 9 8   假設在第7個數後切開，前7個是一個回文序列，後4個也是一個回文序列，那麼，不妨從左邊回文串的中心開始，一個順時針，一個逆時針，模擬一下就會發現，答案就是：枚舉切線，左邊最大回文子序列的長度加上右邊回文子序列的長度的最大值。    

#include <cstdio>  
#include <algorithm>  
  
using namespace std;  
  
const int maxn = 1000 + 10;  
  
int n, a[maxn], d[maxn][maxn];  
  
void read(){  
    for(int i = 1; i <= n; i++) scanf("%d", &a[i]);  
}  
  
void solve(){  
    for(int i = 1; i <= n; i++) d[i][i] = 1;  
    for(int len = 2; len <= n; len++)  
        for(int i = 1; i <= n-len+1; i++){  
            int j = i + len - 1;  
            if(a[i] == a[j]) d[i][j] = d[i+1][j-1] + 2;  
            else d[i][j] = max(max(d[i+1][j], d[i][j-1]), d[i+1][j-1]);  
        }  
    int Max = -1;  
    for(int i = 1; i <= n; i++) Max = max(Max, d[1][i] + d[i+1][n]);  
    printf("%d\n", Max);  
}  
  
int main()  
{  
    while(scanf("%d", &n) == 1 && n){  
        read();  
        solve();  
    }  
    return 0;  
}