首页 > 代码库 > HDU 4745 Two Rabbits(DP)
HDU 4745 Two Rabbits(DP)
题目链接: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); }}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。