http://acm.hdu.edu.cn/showproblem.php?pid=4745
比赛的时候一直想的是枚举每个起点然后求最长公共子序列，一直TLE,一直优化无果。
后来看到了过的人都是用最长回文子序列的算法，第一次见到这个算法，学习了。
在这题中我们用dp[i][j]表示一只兔子从i逆时针走，另一只从j顺时针走，可以走到的最长距离。
那么方程就是（与最长公共子序列类似）
dp[i][j]=dp[(i-1+n)%n][（j+1)%n]+2 a[i]==a[j]
dp[i][j]=max{dp[(i-1+n)%n][j],dp[i][（j+1)%n]} a[i]!=a[j]
最后的结果就是枚举一下起点求一个最大值
for(i=0;i<n;++i)
ans=max{dp[i][(i+1)%n],dp[(i-1+n)%n][i],dp[(i-1+n)%n][（j+1)%n]+1}
注意特殊情况
n==1 ans=1
n==2 ans=2
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #define maxlen 1100 5 using namespace std; 6 int dp[maxlen][maxlen]; 7 int a[maxlen]; 8 int n; 9 int dfs(int i,int j) 10 { 11 if(dp[i][j]) 12 return dp[i][j]; 13 if((i-1+n)%n==j) 14 return dp[i][j]=1+(a[i]==a[j]); 15 int ans=0; 16 if(a[i]==a[j]) 17 ans=dfs((i-1+n)%n,(j+1)%n)+2; 18 else 19 ans = max(ans,max(dfs((i-1+n)%n,(j)%n),dfs((i)%n,(j+1)%n))); 20 return dp[i][j]=ans; 21 } 22 int main () 23 { 24 while(scanf("%d",&n),n) 25 { 26 for(int i=0;i<n;++i) 27 scanf("%d",&a[i]); 28 if(n<3) 29 { 30 printf("%d ",n); 31 continue; 32 } 33 memset(dp,0,sizeof(dp)); 34 for(int i=0;i<=n;++i) 35 dp[i][i]=1; 36 int ans=0; 37 for(int i=0;i<n;++i) 38 { 39 ans = max(ans,max(dfs(i, (i+1)%n), max(dfs((i-1+n)%n, i),dfs((i-1+n)%n, (i+1)%n) + 1))); 40 } 41 printf("%d ",ans); 42 } 43 }