题目链接

http://acm.hdu.edu.cn/showproblem.php?pid=4745

题解转自

https://my.oschina.net/u/4402652/blog/3524396

题目大意

给n个环状的数，A、B两个兔子沿相反的方向走，每次走一步，要求两个兔子每次到达的数要相同，（限制在一圈的范围内），问兔子最远能走几步。

解题思路

首先，把环倍增改成链，接下来找符合题意的最大步数
用dp[i][j]表示在区间[i,j]内，兔子能走的最大步数

初始化dp，预处理问题的子结构，如果a[i]==a[j] , dp[i][j]=dp[i+1][j-1]+2
如果 a[i]!=a[j], dp[i][j]=max(dp[i+1][j],dp[i][j-1])
我把大佬题解里的这部分删了，我觉得任何情况下都要去判断 dp[i][j]=max(dp[i][j],max(dp[i+1][j],dp[i][j-1]))(对不住了大佬Orz，我不知道对不对，或许可以推出只有不等的时候才需要max俩dp)

最后输出最大步数，这里要考虑两种情况：
因为题目要求是：两个兔子往反方向走，并且要求范围限制在一圈之内。
1、如果两个兔子的开始起点不相同，那么每个兔子由起点i能走的最远位置为i+n-1；所以最后的结果是枚举dp[i][i+n-1]的最大值
2、如果开始起点相同，那么第一个起点肯定符合题目要求，跳过这个点直接从下一个点开始判断，最后的结果是枚举dp[i][i+n-2]+1的最大值

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int n;
int a[N<<1],dp[N<<1][N<<1];
int main(){
    while(cin>>n&&n){
        memset(dp,0,sizeof dp);
        for(int i=1;i<=n;i++){
            cin>>a[i];
            a[i+n]=a[i];
            dp[i][i]=1;
            dp[i+n][i+n]=1;
        }
        for(int len=2;len<=n;len++)
            for(int L=1;L+len-1<=n+n;L++){
                int R=len+L-1;
                if(a[L]==a[R]) dp[L][R]=dp[L+1][R-1]+2;
                dp[L][R]=max(dp[L][R],max(dp[L+1][R],dp[L][R-1]));
            }
        int ans=0;
        for(int i=1;i<=n;i++){//精髓
            ans=max(ans,dp[i][i+n-1]);
            ans=max(ans,dp[i][i+n-2]+1);
        } 
        cout<<ans<<endl;
    }    
}