FZU 1040(基因序列相似性问题-CLCS)

Problem 1040 基因序列相似性问题

Accept: 59    Submit: 548
Time Limit: 1000 mSec    Memory Limit : 32768 KB

Problem Description

Genotype 是一个有限的基因序列集。它的每个成员都是由大写的英文字母A-Z组成,不同的字母表示不同种类的基因。一个基因种类可以分化成为若干新的基因种类。这种分化一般呈树状结构。树根处的基因序列称为母序列。基因序列中含有母序列的基因子序列称为本质基因子序列。生物信息学家们在研究Genotype 基因序列时,需要研究同一种类基因序列的相似性。对于同一种类的2个基因序列X和Y,已知它们的母序列P,基因序列X和Y的最长公共本质基因子序列给出其相似性的准确刻画。为了有效地分析基因序列的相似性,科学家们希望设计出一个高效的计算程序,能对给定的基因序列X,Y和它们的母序列P,快速计算出基因序列X和Y的最长公共本质基因子序列的长度。

编程任务:
给定基因序列X,Y和母序列P,计算出基因序列X和Y的最长公共本质基因子序列的长度。

Input

输入数据的前3行中每行有一个正整数,分别表示序列X,Y和P的长度m,n和r(1≤m,n,r≤1000)。接下来的3行给出序列X,Y和P。

Output

在屏幕上输出基因序列X和Y的最长公共本质基因子序列的长度。如果基因序列X和Y没有以P为母序列的公共本质基因子序列,则输出0。

Sample Input

331ABCBCAA

Sample Output

1

这题是为了找省选题无意发现的,原问题的加强版。

解法:

首先我有一个用i滚动的做法,反正是T了,正误不明。。。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<functional>
#include<iostream>
#include<cstdlib>
using namespace std;
#define MAXN (1000+10)
int f[2][MAXN][MAXN];
char a[MAXN],b[MAXN],c[MAXN];
int n,m,p;
int main()
{
    freopen("fzu1040.out","r",stdin);
    while (scanf("%d%d%d",&n,&m,&p)==3)
    {
        scanf("%s%s%s",a+1,b+1,c+1);
        memset(f,0,sizeof(f));
        for (int i=1;i<=n;i++)
        {
            for (int j=1;j<=m;j++)
                for (int k=0;k<=min(i,j);k++)
                {
                    f[i%2][j][k]=max(f[i%2][j-1][k],f[(i-1)%2][j][k]);
                    if (k&&(a[i]==b[j]&&b[j]==c[k])&&(f[(i-1)%2][j-1][k-1]||k==1)) f[i%2][j][k]=max(f[(i-1)%2][j-1][k-1]+1,f[i%2][j][k]);
                    if ((a[i]==b[j])&&(f[(i-1)%2][j-1][k]||k==0)) f[i%2][j][k]=max(f[(i-1)%2][j-1][k]+1,f[i%2][j][k]);
                }
            for(int j=1;j<=m;j++)
                for (int k=1;k<=p;k++)
                    f[(i+1)%2][j][k]=0;
        }
    if (f[n%2][m][p]<p) cout<<"0"<<endl;
    else cout<<f[n%2][m][p]<<endl;
    }
    return 0;
}