题解 P2364 【胖男孩】

wzxx · 2017-08-29 23:07:06 · 题解

DP

话说这道题是一道LCS（最长公共子序列）的升级版：求三个字符串的最长公共子序列（不懂LCS的上网查）。

其实也很简单，基本把求两个字符串的LCS照搬过来。

f[i][j][l]表示第一个字符串的前i个字符与第二个字符串的前j个字符以及第三个字符串前l个字符组成的最长公共子序列。

接着，我们可以得出以下结论：

(1)当i，j，l任意一者等于0时，f[i][j][l]=0。（前0个，也就是没有嘛）

(2)当A[i-1]==B[j-1]&&B[j-1]==C[l-1]时（A，B，C分别表示三个字符串），f[i][j][l]就等于A的前i-1个字符，B的前j-1个字符，C的前l-1个字符组成的最长公共子序列+1，即f[i][j][l]=f[i-1][j-1][l-1]+1。

(3)若以上两种情况都不满足，我们就可以在以下几种情况中求最大值：

           <1>f[i-1][j][l]
           <2>f[i][j-1][l]
           <3>f[i][j][-1l]
           <4>f[i-1][j-1][l]
           <5>f[i-1][j][l-1]
           <6>f[i][j-1][l-1] 
           <7>f[i-1][j-1][l-1]

简单的来说，就是看看哪种情况的最长公共子序列最长，每一个状态都是这样一步一步推过来的。 然后，我们就做完了。

附代码：

#include<iostream>
#include<string>
#include<cstdio>
#include<cstring>
    using namespace std;
//w记录最长公共子序列的长度，st记录最长公共子序列
//P.S:w貌似可以不要，因为最长公共子序列的长度就是st的长度
struct dp
{
    int w; 
    string st;
}F[105][105][105];//F[i][j][l]不解释 
dp Mx(dp a,dp b)//比较函数 
{
    if(a.w>b.w) return a;
    return b;
}
    char A[105],B[105],C[105];
int main()
{
    gets(A); gets(B); gets(C);//输入 
    int len1=strlen(A),len2=strlen(B),len3=strlen(C);//求长度 
    for(int i=0;i<=len1;i++)
        for(int j=0;j<=len2;j++)
            for(int l=0;l<=len3;l++)
                if(i==0||j==0||l==0) F[i][j][l].w=0;//第一种情况 
                else if(A[i-1]==B[j-1]&&B[j-1]==C[l-1])//第二种情况 
                         {
                             F[i][j][l].w=F[i-1][j-1][l-1].w+1;//更新长度 
                             F[i][j][l].st=F[i-1][j-1][l-1].st+A[i-1];//更新字符串 
                         }
                    //第三种情况，有点长...... 
                else F[i][j][l]=Mx(F[i-1][j][l],Mx(F[i][j-1][l],Mx(F[i][j][l-1],Mx(F[i-1][j-1][l],Mx(F[i-1][j][l-1],Mx(F[i][j-1][l-1],F[i-1][j-1][l-1]))))));
    cout<<F[len1][len2][len3].st;//输出 
    return 0;
}