UVa 531 Compromise：DP&LCS

UVa 531 Compromise：DP&LCS2014-07-28 synapse7

531 - Compromise

Time limit: 3.000 seconds

http://uva.onlinejudge.org/index.php？option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=472

注意用一个全局变量flag来确定是否输出空格。

完整代码：

/*0.029s*/#include<bits/stdc++.h>using namespace std;char a[105][35], b[105][35];int dp[105][105], path[105][105];bool first;///建议用全局变量调整空格的输出与否void printlcs（int i, int j）{if （i == 0 || j == 0） return;if （path[i][j] == 1）{printlcs（i - 1, j - 1）;if （first）{printf（"%s", a[i]）;first = false;}else printf（" %s", a[i]）;}else if （path[i][j] == 2） printlcs（i - 1, j）;else printlcs（i, j - 1）;}int main（）{int lena, lenb, i, j;while （~scanf（"%s", a[1]））{if （a[1][0] ！= "#"）for （lena = 2; scanf（"%s", a[lena]）, a[lena][0] ！= "#"; ++lena）;for （lenb = 1; scanf（"%s", b[lenb]）, b[lenb][0] ！= "#"; ++lenb）;memset（dp, 0, sizeof（dp））;for （i = 1; i < lena; ++i）for （j = 1; j < lenb; ++j）{if （strcmp（a[i], b[j]） == 0）dp[i][j] = dp[i - 1][j - 1] + 1, path[i][j] = 1;else if （dp[i - 1][j] >= dp[i][j - 1]）dp[i][j] = dp[i - 1][j], path[i][j] = 2;elsedp[i][j] = dp[i][j - 1], path[i][j] = 3;}first = true;printlcs（lena - 1, lenb - 1）;putchar（10）;}return 0;}