描述
给定3个字符串，求它们的最长公共子序列。
输入
第一行一个整数n，表示三个字符串的长度
接下来三行，每行是一个长度为n只包含小写字母的字符串。
输出
输出最长公共子序列的长度。
输入样例
4
abac
abbc
cbca
输出样例
2
提示
30% n<=10
100% n<=120
三维DP，道理和两个字符串的LCS差不多。
状态转移方程：
f[ i ][ j ][ k ]=max(f[ i ][ j ][ k - 1 ],max(f[ i - 1 ][ j ][ k ],f[ i ][ j - 1 ][ k ]));
if(a[ i ]==b[ j ]&&a[ i ]==c[ k ])
f[ i ][ j ][ k ]=max(f[ i ][ j ][ k ],f[ i - 1 ][ j - 1 ][ k - 1 ]+1);
1 #include<cstdio>
2 #include<iostream>
3 #include<cstring>
4 const int maxn=155;
5 char a[maxn],b[maxn],c[maxn];
6 int f[maxn][maxn][maxn];
7 int lena,lenb,lenc;
8 inline void read()
9 {
10 int n;scanf("%d",&n);
11 scanf("%s",a+1);lena=strlen(a+1);
12 scanf("%s",b+1);lenb=strlen(b+1);
13 scanf("%s",c+1);lenc=strlen(c+1);
14 return ;
15 }
16 inline int max(int x,int y)
17 {
18 if(x<y)return y;
19 return x;
20 }
21 inline void solve1()
22 {
23 memset(f,-1,sizeof(f));
24 for(int i=0;i<=lena;i++)
25 for(int j=0;j<=lenb;j++)
26 f[i][j][0]=0;
27 for(int i=0;i<=lena;i++)
28 for(int j=0;j<=lenc;j++)
29 f[i][0][j]=0;
30 for(int i=0;i<=lenb;i++)
31 for(int j=0;j<=lenc;j++)
32 f[0][i][j]=0;
33 return ;
34 }
35 inline void solve2()
36 {
37 for(int i=1;i<=lena;i++)
38 for(int j=1;j<=lenb;j++)
39 for(int k=1;k<=lenc;k++)
40 {
41 f[i][j][k]=max(f[i][j][k-1],max(f[i-1][j][k],f[i][j-1][k]));
42 if(a[i]==b[j]&&a[i]==c[k])
43 f[i][j][k]=max(f[i][j][k],f[i-1][j-1][k-1]+1);
44 }
45 printf("%d",f[lena][lenb][lenc]);
46 return ;
47 }
48 int main()
49 {
50 freopen("subq.in","r",stdin);
51 freopen("subq.out","w",stdout);
52 read();
53 solve1();
54 solve2();
55 return 0;
56 }