LCS问题。基金会DP。
我很伤心WA非常多。就在LCS问题，需要记录什么路。
反正自己的纪录path错误，最后，就容易上当。
没有优化，二维阵列，递归打印，cin.eof() 来识别 end of file 标识。
至于单词用map 映射的。
事实上也用不着，直接二维string或者 二维char 然后strcmp 也行。
Special Judge
交 UVA 531 奇怪的PE了。
。。 然后改成 flag 标记 输出 空格。最终都AC了。
#include<cstdio>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<stack>
#include<iostream>
#include<list>
#include<set>
#include<bitset>
#include<vector>
#include<cmath>#define INF 0x7fffffff
#define eps 1e-8
#define LL long long
#define PI 3.141592654
#define CLR(a,b) memset(a,b,sizeof(a))
#define FOR(i,a,b) for(int i=a;i<b;i++)
#define FOR_(i,a,b) for(int i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define ft first
#define sd second
#define sf scanf
#define pf printf
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(),(v).end()
#define acfun std::ios::sync_with_stdio(false)#define SIZE 1000 +1
using namespace std;int a[SIZE],b[SIZE];
int dp[SIZE][SIZE];
int path[SIZE][SIZE];
map<string,int>word;
map<int,string>exword;
bool flag;
void print(int i,int j)
{if(i>0&&j>0){if(path[i][j]==0){print(i-1,j-1);if(flag)cout<<" ";elseflag=1;cout<<exword[a[i-1]];}else if(path[i][j]==1)print(i-1,j);else if(path[i][j]==-1)print(i,j-1);}
}
int main()
{acfun;while(1){string tmp;word.clear();int cot=1;int la=0,lb=0;flag=0;while(1){cin>>tmp;if(cin.eof())return 0;if(tmp=="#")break;if(word[tmp]==0){word[tmp]=cot++;exword[cot-1]=tmp;}a[la++]=word[tmp];}while(1){cin>>tmp;if(tmp=="#")break;if(word[tmp]==0){word[tmp]=cot++;exword[cot-1]=tmp;}b[lb++]=word[tmp];}FOR(i,0,la)FOR(j,0,lb){if(a[i]==b[j]){dp[i+1][j+1]=dp[i][j]+1;path[i+1][j+1]=0;}else{if(dp[i+1][j]>=dp[i][j+1]){dp[i+1][j+1]=dp[i+1][j];path[i+1][j+1]=-1;}else{dp[i+1][j+1]=dp[i][j+1];path[i+1][j+1]=1;}}}//cout<<dp[la][lb]<<endl;print(la,lb);cout<<endl;}
}
版权声明：本文博客原创文章，博客，未经同意，不得转载。
