poj 2250 最长公共子序列

记录路径的最长公共子序列。。

简单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;
	}
}