本文主要是介绍UVa 531 Compromise (DPLCS)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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;
}
这篇关于UVa 531 Compromise (DPLCS)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
