首页 > 代码库 > HDU 4745 Two Rabbits（DP）

HDU 4745 Two Rabbits（DP）

2024-07-08 23:43:26   221人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4745

题意：n个数排成一个环。两个人AB初始时各自选定一个位置。每一轮A在顺时针方向选择一个位置，B在逆时针选择一个位置，且这两个人所选位置的数字相等，然后格子跳到新选的位置上。问最多进行多少轮？有一个限制为每次跳跃不能跨过以前自己曾经选过的格子。

思路：主要是分析问题的本质。其实就是求最长回文子列。f[i][j]为[i,j]的最长回文子列，则答案为max(f[1][i],f[i+1][n])。

 

int a[N],f[N][N],n;int main(){    Rush(n)    {        if(n==0) break;        int i,j,k;        clr(f,0);        FOR1(i,n) RD(a[i]),f[i][i]=1;        for(k=2;k<=n;k++)        {            for(i=1;i+k-1<=n;i++)            {                j=i+k-1;                f[i][j]=max(f[i+1][j],f[i][j-1]);                if(a[i]==a[j]) f[i][j]=max(f[i][j],f[i+1][j-1]+2);            }        }        int ans=0;        FOR1(i,n) upMax(ans,f[1][i]+f[i+1][n]);        PR(ans);    }}

 

 

 


联系
我们