题解 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)若以上两种情况都不满足，我们就可以在以下几种情况中求最大值：
```cpp
<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]
```
简单的来说，就是看看哪种情况的最长公共子序列最长，每一个状态都是这样一步一步推过来的。
然后，我们就做完了。
附代码：
```cpp
#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;
}
```