首页 > 代码库 > hdu-4745 Two Rabbits
hdu-4745 Two Rabbits
题目是求最长回文子序列的长度,不过其区间的选取是有点讲究的。
首先把源串复制一遍,放在后面以解决循环的问题。随后用动态规划求其最长回文子序列。这里不能直接把最大值求出来就完事,题目要求了不能走重复的路,换言之,其区间窗口最长只能为n。
一开始我以为只要把最大值求出来和n取min就好,之后发现这个最大值不一定能满足不走重复路的约定,所以我们在查找区间的时候,要控制区间长度。取dp[i][i+n-1]这还没完,比如1213这种数据,可以从3开始最后跳到2,回文串为1213121,如果用n去控制则会输出3下,显然不对。究其原因,是回文串的中心位可以为一个单独的数,所以其长度有奇偶之分,所以窗口大小也要能同时处理奇偶,这里就可以用dp[i][i+n-2]+1了将dp窗口-1,那减去的一位作为起跳点。
直接上代码吧。
#include <iostream> #include <cstring> #include <algorithm> #include <cstdio> using namespace std; int s1[2005]; int dp[2005][2005]; int main() { int n; while(cin>>n) { if(n==0) break; for(int i=0;i<n;i++) { cin>>s1[i],s1[i+n]=s1[i]; } for(int i=0;i<n*2;i++) for(int j=0;j<n*2;j++) dp[i][j]=(i==j); int mx=1; for(int i=n*2-1;i>=0;i--) { for(int j=i+1;j<n*2;j++) { if(i<j) { if(s1[i]==s1[j]) dp[i][j]=dp[i+1][j-1]+2; else dp[i][j]=max(dp[i+1][j],dp[i][j-1]); } } } int ans=0; for(int i=0;i<n;i++) { ans=max(ans,dp[i][i+n-1]); ans=max(ans,dp[i][i+n-2]+1); } cout<<ans<<endl; } return 0; }
hdu-4745 Two Rabbits
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。