游客 注册 | 登录
中文 | En

1783 - 胖男孩

通过次数

0

提交次数

0

时间限制 : 1 秒 内存限制 : 128 MB

麦克正如我们所知的已快乐地结婚，在上个月他胖了70磅。因为手指上的脂肪过多，使他连给他最亲密的朋友斯拉夫克写一个电子邮件都很困难。

    每晚麦克都详细地描述那一天他所吃的所有东西，但有时当他只想按一次某键时往往会按了不止一次，并且他的胖手指还会碰到他不想要按的键，麦克也知道自己的手指有问题，因此他在打字的时候很小心，以确保每打一个想要的字符时误打的字符不超过3个，误打的字符可能在正确字符之前也可能在其之后。

当斯拉夫克多次收到读不懂的电子邮件后，他总是要求麦克将电子邮件发3遍，使他容易读懂一点。

编写程序，帮助斯拉夫克根据他所收到的三封电子邮件求出麦克可能写出的最长的信。

题目输入

输入文件包含了三行文本。每一行文本包括麦克信件的一种版本。其中所有的字符都由英文字母表中的小写字母组成并且不超过100个。

题目输出

输出文件中第一行即唯一的一行数据应该包含斯拉夫克根据所收到的电子邮件推测出的最长信件。你可以相信问题一定有解，但解不一定是唯一的。

输入/输出样例

输入格式

cecqbhvaiaedpibaluk
cabegviapcihlaaugck
adceevfdadaepcialaukd

输出格式

cevapiluk

C++解答

#include<iostream>
#include<fstream>
#include<algorithm>
#include<string>
#include<cstring>
using namespace std;
const int N=101;
string s1,s2,s3;
string F[N][N][N];char ff[5][5][5];
inline bool f(int i,int j,int k){return s1[i-1]==s2[j-1]&&s2[j-1]==s3[k-1];}
inline const string& maxs(const string &a,const string &b){return (a.size()>b.size())?a:b;}
int main(){
    ios::sync_with_stdio(0);
    cin>>s1>>s2>>s3;
    int n1,n2,n3;
    n1=s1.size();n2=s2.size();n3=s3.size();
    for(int i=1;i<=4;i++)
        for(int j=1;j<=4;j++)
            for(int k=1;k<=4;k++){
                if(f(i,j,k))F[i][j][k]=F[i-1][j-1][k-1]+s1[i-1];
                else F[i][j][k]=maxs(maxs(F[i][j][k-1],F[i][j-1][k]),F[i-1][j][k]);
            }
    for(int i=1;i<=n1;i++)
        for(int j=1;j<=n2;j++)
            for(int k=1;k<=n3;k++){
                if(F[i][j][k]=="")continue;
                memset(ff,0,sizeof(ff));
                for(int ai=1;ai<=4&&i+ai<=n1;ai++)
                    for(int aj=1;aj<=4&&j+aj<=n2;aj++)
                        for(int ak=1;ak<=4&&k+ak<=n3;ak++){
                            if(f(ai+i,aj+j,ak+k))ff[ai][aj][ak]=s1[ai+i-1];
                            else if(ff[ai-1][aj][ak])ff[ai][aj][ak]=ff[ai-1][aj][ak];
                            else if(ff[ai][aj-1][ak])ff[ai][aj][ak]=ff[ai][aj-1][ak];
                            else if(ff[ai][aj][ak-1])ff[ai][aj][ak]=ff[ai][aj][ak-1];
                        }
                for(int ai=1;ai<=4&&i+ai<=n1;ai++)
                    for(int aj=1;aj<=4&&j+aj<=n2;aj++)
                        for(int ak=1;ak<=4&&k+ak<=n3;ak++)
                            if(ff[ai][aj][ak])
                                F[i+ai][j+aj][k+ak]=F[i][j][k]+ff[ai][aj][ak];
            }
    cout<<F[n1][n2][n3]<<endl;
    return 0;
}
请先登陆