hdu 1503(最长公共子序列的升级版）

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1503

思路：如何求最长公共子序列就不说了，另外如果有str2[j]==str1[i],那就mark[i]=j,相当于一个标记。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 #define MAXN 111
 7 int dp[MAXN][MAXN];
 8 char str1[MAXN],str2[MAXN];
 9 int mark[MAXN];
10 int path[MAXN][MAXN];
11 int len1,len2;
12 
13 int main(){
14     while(~scanf("%s%s",str1,str2)){
15         len1=strlen(str1);
16         len2=strlen(str2);
17         memset(dp,0,sizeof(dp));
18         memset(path,0,sizeof(path));
19         memset(mark,-1,sizeof(mark));
20         for(int i=1;i<=len1;i++){
21             for(int j=1;j<=len2;j++){
22                 if(str1[i-1]==str2[j-1]){
23                     dp[i][j]=dp[i-1][j-1]+1;
24                 }else if(dp[i-1][j]>dp[i][j-1]){
25                     dp[i][j]=dp[i-1][j];
26                     path[i][j]=1;
27                 }else {
28                     dp[i][j]=dp[i][j-1];
29                     path[i][j]=2;
30                 }
31             }
32         }
33         for(int i=len1,j=len2;i>=1&&j>=1;){
34             if(path[i][j]==0){
35                 i--,j--;
36                 mark[i]=j;
37             }else if(path[i][j]==1){
38                 i--;
39             }else 
40                 j--;
41         }
42         int k=0;
43         for(int i=0;i<len1;i++){
44             if(mark[i]==-1){
45                 printf("%c",str1[i]);
46             }else {
47                 for(int j=k;j<=mark[i];j++){
48                     printf("%c",str2[j]);
49                 }
50                 k=mark[i]+1;
51             }
52         }
53         for(int j=k;j<len2;j++)printf("%c",str2[j]);
54         puts("");
55     }
56     return 0;
57 }
58 
59             
60 
61 
62 
63

View Code