CSU 1060 Nearest Sequence

题意：求三个序列的最长公共子序列。

思路：一开始以为只要求出前两个的LCS，然后和第三个再求一遍LCS就是答案了。但是样例就对我进行啪啪啪打脸了。实际上就跟两个序列的差不多，换成三维的就行了。

代码：需要注意的是max速度比较慢，最后改成if

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<iostream>
 4 using namespace std;
 5 const int N=111;
 6 int dp[N][N][N];
 7 char a[N],b[N],c[N];
 8 void LCS()
 9 {
10     int la=strlen(a),lb=strlen(b),lc=strlen(c),i,j,k;
11     memset(dp,0,sizeof(dp));
12     for(i=1;i<=la;i++)
13     {
14         for(j=1;j<=lb;j++)
15         {
16             for(k=1;k<=lc;k++)
17             {
18                 if(a[i-1]==b[j-1]&&a[i-1]==c[k-1])
19                     dp[i][j][k]=dp[i-1][j-1][k-1]+1;
20                 else
21                 {
22                     if(dp[i-1][j][k]>dp[i][j][k])    dp[i][j][k]=dp[i-1][j][k];
23                     if(dp[i-1][j-1][k]>dp[i][j][k])    dp[i][j][k]=dp[i-1][j-1][k];
24                     if(dp[i-1][j][k-1]>dp[i][j][k])    dp[i][j][k]=dp[i-1][j][k-1];
25                     if(dp[i][j-1][k]>dp[i][j][k])    dp[i][j][k]=dp[i][j-1][k];
26                     if(dp[i][j-1][k-1]>dp[i][j][k])    dp[i][j][k]=dp[i][j-1][k-1];
27                     if(dp[i][j][k-1]>dp[i][j][k])    dp[i][j][k]=dp[i][j][k-1];
28                 }
29             }
30         }
31     }
32 }
33 int main()
34 {
35     while(scanf("%s%s%s",a,b,c)!=EOF)
36     {
37         LCS();
38         printf("%d
",dp[strlen(a)][strlen(b)][strlen(c)]);
39     }
40     return 0;
41 }