lightoj1110_LCS并输出

题目链接：http://lightoj.com/volume_showproblem.php?problem=1110

给定两个字符串，求两个串的最长公共子序列，输出字典序最小的子序列...

解题思路：按照LCS的思路，找寻的时候并判断字典序即可

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <cstring>
 4 #include <cstdlib>
 5 #include <cstdio>
 6 #include <vector>
 7 #include <ctime>
 8 #include <queue>
 9 #include <list>
10 #include <set>
11 #include <map>
12 using namespace std;
13 #define INF 0x3f3f3f3f
14 typedef long long LL;
15 
16 char s1[110], s2[110];
17 char dp[110][110][110];
18 int main()
19 {
20     int t;
21     scanf("%d", &t);
22     for(int ca = 1; ca <= t; ca++)
23     {
24         scanf("%s %s", s1+1, s2+1);
25         int l1 = strlen(s1+1), l2 = strlen(s2+1);
26         memset(dp, 0, sizeof(dp));
27         for(int i = 1; i <= l1; i++)
28         {
29             for(int j = 1; j <= l2; j++)
30             {
31                 if(s1[i] == s2[j])
32                 {
33                     int l = strlen(dp[i-1][j-1]);
34                     strcpy(dp[i][j], dp[i-1][j-1]);
35                     dp[i][j][l] = s1[i]; 
36                 }
37                 else
38                 {
39                     int la = strlen(dp[i-1][j]);
40                     int lb = strlen(dp[i][j-1]);
41                     if(la > lb)
42                         strcpy(dp[i][j], dp[i-1][j]);
43                     else if(la < lb)
44                         strcpy(dp[i][j], dp[i][j-1]);
45                     else
46                     {
47                         if(strcmp(dp[i-1][j], dp[i][j-1]) > 0)
48                             strcpy(dp[i][j], dp[i][j-1]);
49                         else
50                             strcpy(dp[i][j], dp[i-1][j]);
51                     }
52                 }
53             }
54         }
55         printf("Case %d: ", ca);
56         int len = strlen(dp[l1][l2]);
57         if(len == 0)
58             puts(":(");
59         else
60             puts(dp[l1][l2]);
61     }
62     return 0;
63 }