记录路径的最长公共子序列。。
简单dp,开一个pre数组记录路径,由于 dp[i][j]只能有三种状态推过来,即dp[i-1][j-1],dp[i][j-1],dp[i-1][j],那么我们可以将pre[i][j]分别设为 0 1 2 ,最后只要递归扫一遍就可以了。。
#include<iostream>
#include<sstream>
#include<string>
#include<algorithm>
using namespace std;
const int maxn=105;
string s[2][maxn];
int dp[maxn][maxn];
int pre[maxn][maxn];
int len[2];
void getlcs(){
for(int i=0;i<len[0];i++){
dp[i][0]=0;
for(int j=0;j<len[1];j++){
dp[0][j]=0;
if(s[0][i]==s[1][j]){
dp[i+1][j+1]=dp[i][j]+1;
pre[i+1][j+1]=0;
}
else {
if(dp[i+1][j]>dp[i][j+1])dp[i+1][j+1]=dp[i+1][j],pre[i+1][j+1]=1;
else dp[i+1][j+1]=dp[i][j+1],pre[i+1][j+1]=2;
}
}
}
}
void printpre(int len0,int len1){
if(len0==0||len1==0)return;
if(pre[len0][len1]==0){
printpre(len0-1,len1-1);
if(len0==1)cout<<s[0][len0-1];
else cout<<" "<<s[0][len0-1];
}
else if(pre[len0][len1]==1)printpre(len0,len1-1);
else printpre(len0-1,len1);
}
int main(){
string input;
while(cin>>s[0][0]){
for(int i=0;i<2;i++){
int cnt=(i==0?1:0);
while(1){
getline(cin,input);
stringstream sin(input);
while(sin>>input){
if(input=="#")goto endinput;
else s[i][cnt++]=input;
}
}
endinput:;
len[i]=cnt;
}
getlcs();
//cout<<dp[len[0]][len[1]]<<endl;
printpre(len[0],len[1]);
cout<<endl;
}
}
分享到:
相关推荐
LMS Longest Monotonically Increasing Sequence Algorithm
POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类POJ分类
poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题报告poj 解题...
POJ第1861题源码 POJ第1861题源码 POJ第1861题源码
poj分类poj分类poj分类poj分类
* 较为复杂的动态规划:例如 poj1191、poj1054、poj3280、poj2029、poj2948、poj1925、poj3034。 数学 1. 组合数学: * 加法原理和乘法原理。 * 排列组合。 * 递推关系:例如 poj3252、poj1850、poj1019、poj...
北大POJ1159-Palindrome 解题报告+AC代码
poj 3414解题报告poj 3414解题报告poj 3414解题报告poj 3414解题报告
poj 1012解题报告poj 1012解题报告poj 1012解题报告poj 1012解题报告
poj 2329解题报告poj 2329解题报告poj 2329解题报告poj 2329解题报告
poj 1659解题报告poj 1659解题报告poj 1659解题报告poj 1659解题报告
C语言 poj npu 西工大 C语言Poj答案全完整打包,给有需要的朋友
POJ1503解答 POJ1503解答,正确答案(已通过POJ)
poj题目2775文件子目录源代码,递归经典题目,
poj 百练 题目分类 poj 百练 题目分类
POJ1083的代码,POJ1083的代码,POJ1083的代码
POJ1048,加强版的约瑟夫问题 难度中等
北大POJ2002-Squares 解题报告+AC代码
poj 1001答案
poj1379 给予平面内一个点集; 使用模拟退火求出一个点使该点到上述点集内任意一点最短距离最长。