首页 > 代码库 > HDU 4745 最长回文子序列
HDU 4745 最长回文子序列
题目大意
两只青蛙朝不同方向条,每次都到达值相同的位置,不能重复到达自己到过的地方,且不能飞跃已到过的地方
我们可以理解为这两只青蛙分别把整个序列遍历了一遍,依次走过所有的点,找到最多相同的点的个数,因为朝不同方向,且形成环,所以可以把数组扩大两倍,写两组一样的数组
每次跳完得到的必然可以理解为是一个回文子序列
这里有个例外,就是在已形成的回文子序列下 要是还有多出的点是可以加一的,因为可以令两只青蛙同时在这一点出发再去遍历回文串
DP过程
//DP过程是先从前后两个数距离范围最小的1开始,不断扩大距离,这样可以利用前面小范围来更新大范围
//i在这里可以理解为2个数的距离
for(int i=1;i<n;i++){
for(int j=1;j<=n;j++){
if(a[j] == a[j+i]){
dp[j][j+i] = max(dp[j+1][i+j-1]+2,dp[j][j+i]);
}
else
dp[j][j+i] = max(dp[j+1][j+i],dp[j][j+i-1]);
}
}
然后在范围为n-1的dp值中找最大值
和n-2的范围的dp+1中找最大值
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <algorithm> 5 using namespace std; 6 const int N = 2010; 7 int a[N],n; 8 int dp[N][N]; 9 int main()10 {11 while(~scanf("%d",&n)){12 if(n==0)13 break;14 15 for(int i=1;i<=n;i++){16 scanf("%d",a+i);17 a[n+i] = a[i];18 }19 20 memset(dp,0,sizeof(dp));21 for(int i=1;i<=2*n;i++)22 dp[i][i] = 1;23 24 //DP过程是先从前后两个数距离范围最小的1开始,不断扩大距离,这样可以利用前面小范围来更新大范围25 //i在这里可以理解为2个数的距离26 for(int i=1;i<n;i++){27 for(int j=1;j<=n;j++){28 if(a[j] == a[j+i]){29 dp[j][j+i] = max(dp[j+1][i+j-1]+2,dp[j][j+i]);30 }31 else32 dp[j][j+i] = max(dp[j+1][j+i],dp[j][j+i-1]);33 }34 }35 36 int maxn = 0;37 for(int i=1;i<=n;i++)38 maxn = max(maxn,dp[i][i+n-1]);39 for(int i=1;i<=n;i++)40 maxn=max(maxn,dp[i][i+n-2]+1);41 42 printf("%d\n",maxn);43 }44 return 0;45 }
HDU 4745 最长回文子序列
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。