UVa 531: Compromise

求最長公共子序列（LCS）並打印序列。dp解決，各節點標記最終的序列選擇，最後遞歸打印即可。   我的解題代碼如下：

 
#include <iostream>  
#include <cstdio>  
#include <cstring>  
#include <cstdlib>  
#include <algorithm>  
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<m; i++)  
        {  
            for(int j=0; j<n; j++)  
            {  
                if(!strcmp(P1[i],P2[j]))  
                {  
                    if(!i || !j) dp[i][j] = 1;  
                    else dp[i][j] = dp[i-1][j-1]+1;  
                    PathSel[i][j] = 0;  
                }  
                else if(!i || !j)  
                {  
                    if(i) { dp[i][j] = dp[i-1][j]; PathSel[i][j] = 1;}  
                    if(j) { dp[i][j] = dp[i][j-1]; PathSel[i][j] = 2;}  
                }  
                else if(dp[i-1][j] > 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;  
}