CSU 1060 Nearest Sequence

时间:2024-05-23 08:34:50

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

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

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

 #include<stdio.h>
#include<string.h>
#include<iostream>
using namespace std;
const int N=;
int dp[N][N][N];
char a[N],b[N],c[N];
void LCS()
{
int la=strlen(a),lb=strlen(b),lc=strlen(c),i,j,k;
memset(dp,,sizeof(dp));
for(i=;i<=la;i++)
{
for(j=;j<=lb;j++)
{
for(k=;k<=lc;k++)
{
if(a[i-]==b[j-]&&a[i-]==c[k-])
dp[i][j][k]=dp[i-][j-][k-]+;
else
{
if(dp[i-][j][k]>dp[i][j][k]) dp[i][j][k]=dp[i-][j][k];
if(dp[i-][j-][k]>dp[i][j][k]) dp[i][j][k]=dp[i-][j-][k];
if(dp[i-][j][k-]>dp[i][j][k]) dp[i][j][k]=dp[i-][j][k-];
if(dp[i][j-][k]>dp[i][j][k]) dp[i][j][k]=dp[i][j-][k];
if(dp[i][j-][k-]>dp[i][j][k]) dp[i][j][k]=dp[i][j-][k-];
if(dp[i][j][k-]>dp[i][j][k]) dp[i][j][k]=dp[i][j][k-];
}
}
}
}
}
int main()
{
while(scanf("%s%s%s",a,b,c)!=EOF)
{
LCS();
printf("%d\n",dp[strlen(a)][strlen(b)][strlen(c)]);
}
return ;
}