题目：http://acm.hdu.edu.cn/showproblem.php?pid=4745
题解：首先要抽象出题目要求的是啥。首先对于环的问题， 我们可以倍增成链，然后环的所有情况可以通过链来解决。这道题目由于不用越过自己走过的石头，所以2*n的链就覆盖了所有情况了。然后对于每种情况，要求两个方向的兔子走的位置的权重得一样，由于走的都是同一个环，只是方向不一样，所以两个兔子走的路线一定是一个回文序列，那么这道题目就转化为求最大回文序列长度的问题了。这里的坑点就是，如果两个兔子的起点是重合的话，光算回文序列是取不到最优解的需要特殊处理一下。
ac代码：
#include <cstdio> #include <iostream> #include <cstring> #include <queue> #define mt(a) memset(a,0,sizeof(a)) using namespace std; int dp[2002][2002]; int s[2002]; int main() { int n; while(~scanf("%d",&n)&&n) { for(int i=1;i<=n;i++) { scanf("%d",&s[i]); s[i+n]=s[i]; dp[i][i]=dp[i+n][i+n]=1; } for(int l=2;l<=2*n;l++) { for(int i=1;i+l-1<=2*n;i++) { int j=i+l-1; dp[i][j]=max(dp[i+1][j],dp[i][j-1]); if(s[i]==s[j]) dp[i][j]=max(dp[i][j],dp[i+1][j-1]+2); } } int ans=0; for(int i=1;i<=n;i++) { ans=max(dp[i][i+n-1],ans); ans=max(dp[i][i+n-2]+1,ans); } cout<<ans<<endl; } return 0; }