题目链接:http://poj.org/problem?id=2250
解题报告:
1、状态转移方程:
for(i=1; i<=len1; i++) { for(j=1; j<=len2; j++) { dp[i][j]=_max(i,j,dp[i-1][j-1]+same(i-1,j-1),dp[i-1][j],dp[i][j-1]); } }
2、记录决策
3、反序输出
#include <iostream> #include <string.h> #include <cstdio> #include <algorithm> using namespace std; #define MAXV 110 #define MAXN 35 char stemp[MAXN]; char s1[MAXV][MAXN]; char s2[MAXV][MAXN];///记录单词 int len1,len2;///单词长度 int dp[MAXV][MAXV]; ///dp[i][j]表示s1的前i个单词,和s2的前j个单词,最长公共子单词 int p[MAXV][MAXV]; ///决策,如果s1的第i个单词,和s2的第j个单词相同,则为1,以便输出使用 int pos[MAXV]; ///输出结果 int sum; ///有几个单词 int _max(int i,int j,int a,int b,int c) { if(a>b&&a>c) { p[i][j]=1; ///记录决策 return a; } else if(b>a&&b>c) { p[i][j]=2; return b; } p[i][j]=3; return c; } int same(int x,int y) { if(!strcmp(s1[x],s2[y])) return 1; return 0; } void print(int i,int j) { if(p[i][j]==1) ///即s1的第i个单词,和s2的第j个单词相同 { pos[sum++]=i-1; ///记录这个单词的位置 print(i-1,j-1); } else if(p[i][j]==2) print(i-1,j); else if(p[i][j]==3) print(i,j-1); } int main() { int i,j; /// Input /// while(scanf("%s",stemp)!=EOF) { len1=len2=0; strcpy(s1[len1++],stemp); while(1) { scanf("%s",stemp); if(!strcmp(stemp,"#")) break; strcpy(s1[len1++],stemp); } while(1) { scanf("%s",stemp); if(!strcmp(stemp,"#")) break; strcpy(s2[len2++],stemp); } /// DP /// memset(dp,0,sizeof(dp)); memset(p,0,sizeof(p)); for(i=1; i<=len1; i++) { for(j=1; j<=len2; j++) { dp[i][j]=_max(i,j,dp[i-1][j-1]+same(i-1,j-1),dp[i-1][j],dp[i][j-1]); } } /// Output /// sum=0; print(len1,len2); for(i=sum-1; i>=0; i--) ///反序输出 printf("%s ",s1[pos[i]]); puts(""); } return 0; }