2013 ACM/ICPC Asia Regional Hangzhou Online–1008

hdoj4745 Two Rabbits
想到了就是水dp。。。

#include<stdio.h>
#include<string.h>
int a[2010],dp[2010][2010];
inline int max(int a,int b){return a>b?a:b;}
int main()
{
    int i,j;
    int n;
    while(scanf("%d",&n) && n)
    {
        for(i=1;i<=n;i++) {scanf("%d",&a[i]);a[i+n]=a[i];}
        for(i=1;i<=2*n;i++) dp[i][i]=1;
        for(i=1;i<=2*n-1;i++) dp[i][i+1]=(a[i]==a[i+1]?2:1);
        for(int len=3;len<=n;len++)
        {
            for(i=1;i+len-1<=2*n;i++)
            {
                j=i+len-1;
                dp[i][j]=max(dp[i+1][j],dp[i][j-1]);
                if(a[i]==a[j]) dp[i][j]=max(dp[i][j],dp[i+1][j-1]+2);
            }
        }
        int ans=-1;
        for(i=1;i<=n;i++) ans=max(ans,dp[i][i+n-1]);
        for(i=1;i<=n;i++) ans=max(ans,dp[i][i+n-2]+1);
        printf("%d\n",ans);
    }
    return 0;
}

发表评论

电子邮件地址不会被公开。 必填项已用 * 标注

*

您可以使用这些 HTML 标签和属性: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>