自动搬运

查看原文

来自洛谷，原作者为

	Froranzen 你没有那个实力，不要再欺骗自己了

搬运于2025-08-24 21:36:49，当前版本为作者最后更新于2020-12-26 23:47:08，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

题目传送门~

---

思路

---

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

实现

---

1. $dp[i][j][l]$ 存 3 个字符串前i, j, l 个字符的 $LCS$ 长度。
2. $ans[i][j][l]$ 存 3 个字符串前i, j, l 个字符 的 $LCS$ 内容。

转移方程

---

如果当前的 $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）