T1
【问题描述】
麦克正如我们所知的已快乐地结婚,在上个月他胖了70磅。因为手指上的脂肪过多,使他连给他最亲密的朋友斯拉夫克写一个电子邮件都很困难。 每晚麦克都详细地描述那一天他所吃的所有东西,但有时当他只想按一次某键时往往会按了不止一次,并且他的胖手指还会碰到他不想要按的键,
麦克也知道自己的手指有问题,因此他在打字的时候很小心,以确保每打一个想要的字符时误打的字符不超过3个,误打的字符可能在正确字符之前
也可能在其之后。当斯拉夫克多次收到读不懂的电子邮件后,他总是要求麦克将电子邮件发3遍,使他容易读懂一点。编写程序,帮助斯拉夫克根据
他所收到的三封电子邮件求出麦克可能写出的最长的信。
【输入格式】
输入文件包含了三行文本。每一行文本包括麦克信件的一种版本。其中所有的字符都由英文字母表中的小写字母组成并且不超过100个。
【输出格式】
输出文件有两行,输出最大长度。 你可以相信问题一定有解。
【输入样例1】
cecqbhvaiaedpibaluk cabegviapcihlaaugck adceevfdadaepcialaukd
【输出样例1】
9
【时空限制】
1S 512MB
解:
额,虽然看出来好像是最长的公共子序列,但是我弱到不会写。。。。。。
设f[i][j][k]表示三个序列分别的前i个,前j个,前k个中的最长公共子序列,如果这三个数都相同,则f[i][j][k]=f[i-1][j-1][k-1]+1;否则我们就要考虑上一步的最优情况,这个写在程序注释里。
#include<iostream> #include<cstdio> #include<cstring> using namespace std; string s1,s2,s4,s3,p; int t1,t2,t3,f[400][400][400]; int main() { cin>>s1>>s2>>s3; string p="9"; t1=s1.size(); t2=s2.size(); t3=s3.size(); s1=p+s1; s2=p+s2; s3=p+s3; for (int i=1;i<=t1;i++) for (int j=1;j<=t2;j++) for (int k=1;k<=t3;k++) if ((s1[i]==s2[j])&&(s1[i]==s3[k])) f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-1]+1); else { f[i][j][k]=max(f[i][j][k],f[i-1][j][k]);f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k]); f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-1]);f[i][j][k]=max(f[i][j][k],f[i][j-1][k-1]); f[i][j][k]=max(f[i][j][k],f[i-1][j][k-1]);f[i][j][k]=max(f[i][j][k],f[i][j-1][k]); f[i][j][k]=max(f[i][j][k],f[i][j][k-1]); //上一次有这几种情况,选取其中最优的。 } cout<<f[t1][t2][t3]<<endl; return 0; }