题解 P2364 【胖男孩】

· · 题解

题目传送门~

思路

其实这道题目就是求 3 个序列的最长公共子序列（LCS），然后再开一个字符串数组存每次转移后的最长子序列，至于题目中的每打一个想要的字符时误打的字符不超过 3 个，这个条件不需要考虑，因为我们搜出来的 LCS 一定包含正解（主要是SPJ）。

实现

转移方程

如果当前的 a[i] 和 b[j] 和 c[l] 相同（即：有新的公共元素） 那么

dp[i][j][l] = max (dp[i][j][l], dp[i - 1][j - 1][l - 1] +1)

如果不相同，即无法更新公共元素，考虑继承：

dp[i][j][l] = max (dp[i - 1][j][l], dp[i][j - 1][l], dp[i][j][l - 1])

代码奉上

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

char awa[105];
char waw[105];
char aaw[105];
int qwq[105][105][105];
string wqw[105][105][105];

inline int max (int a, int b) {
    return a > b ? a : b;
}

int main () {
    scanf ("%s %s %s", awa, waw, aaw);
    int n, m, k;
    n = strlen (awa);
    m = strlen (waw);
    k = strlen (aaw);
    for (register int i(1); i <= n; ++i)
        for (register int j(1); j <= m; ++j)
            for (register int l(1); l <= k; ++l) {
                if (awa[i - 1] == waw[j - 1] && awa[i - 1]== aaw[l - 1]) { //转移方程
                    if (qwq[i][j][l] < qwq[i - 1][j - 1][l - 1] +1) {
                        qwq[i][j][l] = qwq[i - 1][j - 1][l - 1] +1;
                        wqw[i][j][l] = wqw[i - 1][j - 1][l - 1] + awa[i - 1];  //更新答案
                    } 
                }
                else { //考虑继承
                    if (qwq[i][j][l] < qwq[i - 1][j][l]) {
                        qwq[i][j][l] = qwq[i - 1][j][l];
                        wqw[i][j][l] = wqw[i - 1][j][l]; //更新答案
                    }
                    if (qwq[i][j][l] < qwq[i][j - 1][l]) {
                        qwq[i][j][l] = qwq[i][j - 1][l];
                        wqw[i][j][l] = wqw[i][j - 1][l];
                    }
                    if (qwq[i][j][l] < qwq[i][j][l - 1]) {
                        qwq[i][j][l] = qwq[i][j][l - 1];
                        wqw[i][j][l] = wqw[i][j][l - 1];
                    }
                }
            }
    cout<<wqw[n][m][k];
    return 0;
}

（悄悄要个关注不过分吧，qwq）