题目描述
麦克正如我们所知的已快乐地结婚，在上个月他胖了70磅。因为手指上的脂肪过多，使他连给他最亲密的朋友斯拉夫克写一个电子邮件都很困难。
每晚麦克都详细地描述那一天他所吃的所有东西，但有时当他只想按一次某键时往往会按了不止一次，并且他的胖手指还会碰到他不想要按的键，麦克也知道自己的手指有问题，因此他在打字的时候很小心，以确保每打一个想要的字符时误打的字符不超过3个，误打的字符可能在正确字符之前也可能在其之后。
当斯拉夫克多次收到读不懂的电子邮件后，他总是要求麦克将电子邮件发3遍，使他容易读懂一点。
编写程序，帮助斯拉夫克根据他所收到的三封电子邮件求出麦克可能写出的最长的信。
输入格式
输入文件包含了三行文本。每一行文本包括麦克信件的一种版本。其中所有的字符都由英文字母表中的小写字母组成并且不超过100个。
输出
输出文件中第一行即唯一的一行数据应该包含斯拉夫克根据所收到的电子邮件推测出的最长信件。你可以相信问题一定有解，但解不一定是唯一的。
样例输入
cecqbhvaiaedpibaluk
cabegviapcihlaaugck
adceevfdadaepcialaukd
样例输出
cevapiluk
本人在网上搜索本题题解时发现大多数都是错的，在此列出正确的题解，如有疏漏指出请多多指教。
结题思路：
本题是一道最长公共上升子序列的变形题，难点在于对打错字最多不超多3个的理解，本菜鸟也是想了半天想不出来，最后终于在一位神犇的帮助下才写出来的。打错字最多不超过3个，那么在最坏的情况下两正确的字符间可能间隔6个错误的字符（T F F F F F F T），从此下手f[i][j][k]表示三字符串到达i j k位置时的最长字符。如果 （i j k)位置的字符相同的话从 （i-7) （j-7） （k-7）开始向i j k循环，求出最长的字符串，加上当前的字符即可。详情见参考程序，如有疑问可以留言。
参考程序：
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<string>
using namespace std;
const int N=105;
string f[N][N][N],a,b,c,ans="";
int g[N][N]={0};
int main()
{
int lena,lenb,lenc;
cin>>a>>b>>c;
lena=(int)a.size();
lenb=(int)b.size();
lenc=(int)c.size();
a='0'+a;//我习惯从1开始循环，所以在前面加一个‘0’字符占位用.
b='0'+b;
c='0'+c;
for (int i=1;i<=lena;i++)
for (int j=1;j<=lenb;j++)
for (int l=1;l<=lenc;l++)
f[i][j][l]="";
for (int i=1;i<=lena;i++)
for (int j=1;j<=lenb;j++)
for (int k=1;k<=lenc;k++)
if (a[i]==b[j]&&b[j]==c[k]){
f[i][j][k]=a[i];
for (int x=max(0,i-7);x<i;x++)
for (int y=max(0,j-7);y<j;y++)
for (int z=max(0,k-7);z<k;z++)
if (f[i][j][k].size()<=f[x][y][z].size()+1)
f[i][j][k]=f[x][y][z]+a[i];
if (ans.size()<=f[i][j][k].size())
ans=f[i][j][k];
}
cout<<ans<<endl;
return 0;
}转载自原文链接, 如需删除请联系管理员。
原文链接：胖男孩（DP经典），转载请注明来源！