首页 > 代码库 > Palindromic Subsequence(最长回文字符串 输出路径)
Palindromic Subsequence(最长回文字符串 输出路径)
初看好简单 一开始调试着一直re 后来也不知道怎么就对了 但是还有一些bug存在 ,
这道题的打印路径和light oj An Easy LCS(ps:点击打开链接)一样
但是只改一下会Tle 因为(1000*1000*1000)好大
但是把存储的字符串改为string 定义的就过了
但是还是有一点有点难受(下面会说出)
我也是醉了
#include <stdio.h> #include <string.h> #include <string> #include <iostream> using namespace std; #define maxx 1010 char s1[maxx]; char s2[maxx]; int dp[maxx][maxx]; string s[maxx][maxx]; int main() { while(scanf("%s",s1+1)!=EOF){ memset(dp,0,sizeof(dp)); int k; int n=strlen (s1+1); for(int i=1;i<=n;i++) s2[i]=s1[n-i+1]; for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) { if(s1[i]==s2[j]) { dp[i][j]=dp[i-1][j-1]+1; s[i][j]=s1[i]+s[i-1][j-1]+s2[j]; } else { if(dp[i-1][j]>dp[i][j-1]) { dp[i][j]=dp[i-1][j]; s[i][j]=s[i-1][j]; } else if(dp[i][j-1]>dp[i-1][j]) { dp[i][j]=dp[i][j-1]; s[i][j]=s[i][j-1]; } else { dp[i][j]=dp[i-1][j]; if(s[i-1][j]>s[i][j-1]) s[i][j]=s[i][j-1]; else s[i][j]=s[i-1][j]; } } } string s3= s[n][n];//怎么也没有想到string定义的是这样输出的 int l = dp[n][n]; if(l & 1) { for(int i=0; i<(l-1)/2; i++) cout << s3[i]; for(int i=(l-1)/2; i>=0; i--) cout << s3[i]; } else { for(int i=0; i<l/2; i++) cout << s3[i]; for(int i=l/2-1; i>=0; i--) cout << s3[i]; } cout << endl; } }
Palindromic Subsequence(最长回文字符串 输出路径)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。