UVa 531 Compromise：DP&LCS

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;
                else
                    dp[i][j] = dp[i][j - 1], path[i][j] = 3;
            }
        first = true;
        printlcs(lena - 1, lenb - 1);
        putchar(10);
    }
    return 0;
}

查看本栏目更多精彩内容：http://www.bianceng.cnhttp://www.bianceng.cn/Programming/sjjg/

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索dp
， int
， path
， 空格
， else
first
，以便于您获取更多的相关知识。