首页 > 代码库 > HDU 1503 Advanced Fruits

HDU 1503 Advanced Fruits

2024-07-15 01:19:05   212人阅读

求最短公共祖先，是最长公共子序列的变形。

在DP的同时记录下路径，然后递归回去输出即可。

如果碰到公共的，只输出一次。

 

以第一个样例为例：

图中数字是最大公共子段的长度，下标代表路径。

带下划线的是递归时所走的路径。

 

 1 //#define LOCAL 2 #include <iostream> 3 #include <cstdio> 4 #include <cstring> 5 using namespace std; 6  7 char s1[205], s2[205]; 8 int path[205][205], dp[205][205]; 9 10 void Print(int i, int j)11 {12     if(i == 0 && j == 0)    return;13     if(i == 0 && j != 0)14     {15         Print(i, j-1);16         printf("%c", s2[j-1]);17     }18     else if(i != 0 && j == 0)19     {20         Print(i-1, j);21         printf("%c", s1[i-1]);22     }23     else if(path[i][j] == 0)24     {25         Print(i-1, j-1);26         printf("%c", s1[i-1]);27     }28     else if(path[i][j] == 1)29     {30         Print(i-1, j);31         printf("%c", s1[i-1]);32     }33     else34     {35         Print(i, j-1);36         printf("%c", s2[j-1]);37     }38 }39 40 int main(void)41 {42     #ifdef LOCAL43         freopen("1503in.txt", "r", stdin);44     #endif45 46     while(cin >> s1 >> s2)47     {48         int len1, len2;49         len1 = strlen(s1);50         len2 = strlen(s2);51         int i, j;52         for(i = 1; i <= len1; ++i)53             for(j = 1; j <= len2; ++j)54             {55                 if(s1[i-1] == s2[j-1])56                 {57                     dp[i][j] = dp[i-1][j-1] + 1;58                     path[i][j] = 0;59                 }60                 else if(dp[i-1][j] > dp[i][j-1])61                 {//从上边来62                     dp[i][j] = dp[i-1][j];63                     path[i][j] = 1;64                 }65                 else66                 {//从左边来67                     dp[i][j] = dp[i][j-1];68                     path[i][j] = 2;69                 }70             }71 72         Print(len1, len2);73         printf("\n");74     }75     return 0;76 }
代码君

 


联系
我们