首页 > 代码库 > POJ 2250 Compromise(最长公共子序列LCS)
POJ 2250 Compromise(最长公共子序列LCS)
POJ 2250 Compromise(最长公共子序列LCS)
http://poj.org/problem?id=2250
题意:
给你两段由空格分隔的语句, 要你求该两段语句的最长公共子序列. 且随便输出一个解即可.注意每个单词需要看成我们一般处理字符串子序列的一个单独字符.即每个单词是一个整体.
分析:
与往常计算最长公共子序列一样的方式即可. 然后用DFS输出序列即可.本题与POJ1458提供的解法本质一样.
http://blog.csdn.net/u013480600/article/details/40741333
AC代码:
#include<cstring> #include<cstdio> #include<string> #include<iostream> #include<algorithm> using namespace std; const int maxn=100+5; string s1[maxn]; string s2[maxn]; int n; int m; int dp[maxn][maxn]; void dfs(int i,int j) { if(i==0 || j==0) return ; else if(s1[i]==s2[j]) { dfs(i-1,j-1); cout<<s1[i]<<" ";//输出要放在dfs下面,想想为什么? } else { if(dp[i-1][j]>dp[i][j-1]) dfs(i-1,j); else dfs(i,j-1); } } int main() { string s; while(cin>>s) { n=m=0; if(s!="#") { s1[++n]=s; while(cin>>s && s!="#") { s1[++n]=s; } } while(cin>>s && s!="#") { s2[++m]=s; } //递推过程 memset(dp,0,sizeof(dp)); for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) { if(s1[i]==s2[j]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i-1][j], dp[i][j-1]); } //输出结果 dfs(n,m); cout<<endl; } return 0; }
POJ 2250 Compromise(最长公共子序列LCS)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。