UVa 531: Compromise - c++编程基础

求最长公共子序列（LCS）并打印序列。dp解决，各节点标记最终的序列选择，最后递归打印即可。

我的解题代码如下：

 
#include   
#include   
#include   
#include   
#include   
using namespace std;  
  
#define max(a,b) (a>b a:b)  
#define WORDLEN 32  
#define SENTENCELEN 102  
char P1[SENTENCELEN][WORDLEN], P2[SENTENCELEN][WORDLEN];  
int dp[SENTENCELEN][SENTENCELEN];  
int PathSel[SENTENCELEN][SENTENCELEN];  
  
void PrintSeq(int i, int j)  
{  
    if(i<0 || j<0 || !dp[i][j]) return ;  
    if(!PathSel[i][j])  
    {  
        PrintSeq(i-1,j-1);  
        if(dp[i][j]==1) cout << P1[i];  
        else cout << ' ' << P1[i];  
    }  
    else if(PathSel[i][j]==1) PrintSeq(i-1,j);  
    else PrintSeq(i,j-1);     
}  
int main()  
{  
    int m,n;  
    while(cin >> P1[0])  
    {  
        m = 0, n = 0;  
        while(P1[m++][0]!='#' && cin >> P1[m]) ; m--;  
        while(cin >> P2[n] && P2[n++][0]!='#') ; n--;  
          
        dp[0][0] = 0;  
        for(int i=0; i




 dp[i][j-1])  
                {  
                    dp[i][j] = dp[i-1][j];  
                    PathSel[i][j] = 1;  
                }  
                else  
                {  
                    dp[i][j] = dp[i][j-1];  
                    PathSel[i][j] = 2;  
                }  
            }  
        }  
        PrintSeq(m-1,n-1);  
        cout << endl;  
    }  
    return 0;  
}