HDU 4745---Two Rabbits（區間DP），hdu4745---two

HDU 4745---Two Rabbits（區間DP），hdu4745---two

題目鏈接

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

題意：兩只兔子，在n塊圍成一個環形的石頭上跳躍，每塊石頭有一個權值ai，一只從左往右跳，一只從右往左跳，每跳一次，兩只兔子所在的石頭的權值都要相等，在一圈內（各自不能超過各自的起點，也不能再次回到起點）它們最多能經過多少個石頭(1 <= n <= 1000, 1 <= ai <= 1000)。

分析：其實就是求一個環中，非連續最長回文子序列的長度。dp[i][j] = max{ dp[i + 1][j], d[i][j - 1], （a[i]= =a[j])*dp[i + 1][j - 1] + 2 }
        但是，這個dp公式僅僅是求出一個序列的非連續最長回文子序列，題目的序列是環狀的，有兩種思路：

思路1 代碼如下：

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <set>
using namespace std;
int a[2005];
int dp[2005][2005];

int main()
{
    int n;
    while(scanf("%d",&n)!=EOF&&n)
    {
        for(int i=1;i<=n;i++)
        {
            scanf("%d",&a[i]);
            a[i+n]=a[i];
        }
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=2*n;i++)
            dp[i][i]=1;
        for(int len=1;len<n;len++)
        {
            for(int i=1;i+len<=2*n;i++)
            {
                dp[i][i+len]=max(dp[i][i+len-1],max(dp[i+1][i+len],dp[i+1][i+len-1]+(a[i]==a[i+len])*2));
            }
        }
        int tmp=0;
        for(int i=1;i<=n;i++)
            tmp=max(tmp,dp[i][i+n-1]);
        for(int i=1;i<=n;i++)
            tmp=max(tmp,dp[i][i+n-2]+1);
        cout<<tmp<<endl;
    }
    return 0;
}