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; }
补充:软件开发 , C++ ,