UVA 531 Compromise

最长子序列问题，需要打印路径。作为一个菜鸟，我竟然非要“自创”一种方法，结果是惨痛的。最后还是参考前辈的代码，用一个二维数组记录指向，0表示斜移，1、－1是左移或上移。本来按我的原则抄的代码是不应该贴出来的，但这次我无耻地改了一下再贴，方便以后自己看。

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define MAXN 110
 4 #define MAXM 40
 5 char a[MAXN][MAXM], A, b[MAXN][MAXM], B;
 6 int f[MAXN][MAXN], p[MAXN][MAXN], flag;
 7 int init()
 8 {
 9     int i;
10     A = B = 1;
11     for(;;)
12     {
13         if(scanf("%s", a[A]) != 1)
14             return 0;
15         if(a[A][0] == '#')
16             break;
17         A ++;
18     }
19     for(;;)
20     {
21         scanf("%s", b[B]);
22         if(b[B][0] == '#')
23             break;
24         B ++;
25     }
26 }
27 void printresult(int i, int j)
28 {
29     if(!i || !j)
30         return ;
31     if(p[i][j] == 0)
32     {
33         printresult(i - 1, j - 1);
34         if(flag)
35             printf(" ");
36         else
37             flag = 1;
38         printf("%s", a[i]);
39     }
40     else if(p[i][j] == -1)
41         printresult(i - 1, j);
42     else
43         printresult(i, j - 1);
44 }
45 int main()
46 {
47     while(init())
48     {
49         int i, j;
50         memset(f, 0, sizeof(f));
51         for(i = 1; i < A; i ++)
52             for(j = 1; j < B; j ++)
53             {
54                 if(strcmp(a[i], b[j]) == 0)
55                 {
56                     f[i][j] = f[i - 1][j - 1] + 1;
57                     p[i][j] = 0;
58                 }
59                 else
60                 {
61                     f[i][j] = f[i - 1][j];
62                     p[i][j] = -1;
63                     if( f[i][j - 1] > f[i][j])
64                     {
65                         f[i][j] = f[i][j - 1];
66                         p[i][j] = 1;
67                     }
68                 }
69             }
70         flag = 0;
71         printresult(A - 1, B - 1);
72         printf("\n");
73     }
74     return 0;
75 }