脚本宝典收集整理的这篇文章主要介绍了「题解」蝙蝠侠的麻烦，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。
没 事 找 事
step1：观察题面。 「蝙蝠侠需要找到一个最长的字符串，使得这个字符串作为一个子序列被包含在所有的三个字符串中」，可以得出这是一道最长公共子序列，而且有三个字符串。（题型：线性 dp —— 最长公共子序列） 「蝙蝠侠现在需要找到的是最大的长度，而不是序列」，说明只是一道普通的 LCS。
step2：思考解法。 第一步思考 dp 状态：
(dp_{i,j,k})：第一串前 (i) 项，第二串前 (j) 项，第三串前 (k) 项中的最长公共子序列长度。
对于当前的 (a_{i}, b_{j}, c_{k}) 而言，只有能做贡献或无法做贡献两种状态。 若 (a_{i}= b_{j}= c_{k})，则它们能做贡献，此时的最长公共子序列的长度为第一串前 (i - 1) 项，第二串前 (j - 1) 项，第三串前 (k - 1) 项中的最长公共子序列的长度加 (1)。 否则它们无法做贡献，此时放弃做贡献最小的那一项。 第二步思考状态转移方程： 本题比常规的 LCS 要多一个字符串，因此只需要再多一维就好。
step3：完成代码： 因为有三个字符串，所以需要比平常的 LCS 多一层循环。 代码（抵制学术不端行为，拒绝 Ctrl + C）：
#include <bits/stdc++.h>
using namespace std;
const int N = 5e1 + 5;
char a[N], b[N], c[N];
int la, lb, lc, dp[N][N][N];
/*
dp(i, j, k): 前 i, j, k 项中的最长公共子序列
if a(i) = b(j) = c(k)
dp(i, j, k) = dp(i - 1, j - 1, k - 1) + 1;
else
dp(i, j, k) = max{dp(i - 1, j, k), dp(i, j - 1, k), dp(i, j, k - 1)};
*/
int main() {
freopen("trouble.in", "r", stdin);
freopen("trouble.out", "w", stdout);
scanf("%sn%sn%s", a + 1, b + 1, c + 1);
la = strlen(a + 1), lb = strlen(b + 1), lc = strlen(c + 1);
for (int i = 1; i <= la; i++) {
for (int j = 1; j <= lb; j++) {
for (int k = 1; k <= lc; k++) {
if (a[i] == b[j] && b[j] == c[k]) {
dp[i][j][k] = dp[i - 1][j - 1][k - 1] + 1;
} else {
dp[i][j][k] = max(dp[i - 1][j][k], max(dp[i][j - 1][k], dp[i][j][k - 1]));
}
}
}
}
printf("%d", dp[la][lb][lc]);
return 0;
}
让我们来解决 [『蝙蝠侠的麻烦』] 叭~(http://222.180.160.110:1024/problem/29415)
Bye bye!!1 👋👋
以上是脚本宝典为你收集整理的「题解」蝙蝠侠的麻烦全部内容，希望文章能够帮你解决「题解」蝙蝠侠的麻烦所遇到的问题。
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。