BZOJ-5107: [CodePlus2017]找爸爸

[文章目录]

Description

小A最近一直在找自己的爸爸,用什么办法呢,就是DNA比对。小A有一套自己的DNA序列比较方法,其最终目标是最大化两个DNA序列的相似程度,具体步骤如下:1.给出两个DNA序列,第一个长度为n,第二个长度为m。2.在两个序列的任意位置插入任意多的空格,使得两个字符串长度相同3.逐位进行匹配,如果两个序列相同位置上的字符都不是空格,假设第一个是x,第二个是y,那么他们的相似程度由d(x,y)定义。对于两个序列中任意一段极长的长度为k的连续空格,我们定义这段空格的相似程度为g(k)=-A-B(k-1)。那么最终两个序列的相似程度就是所有的d(x,y)加上所有的极长空格段的相似程度之和。现在小A通过某种奥妙重重的方式得到了小B的DNA序列中的一段,他想请你帮他算一下小A的DNA序列和小B的DNA序列的最大相似程度。
n,m<=3000

显然不存在两个对应位置都是空格的情况,另外连续空格的代价可以看为第一个空格代价为A,其余为B。那么设三个状态,dp[i][j]表示第一个个处理完前i个,第二个处理了前j个的【1.i,j都有值; 2.i空,j有值; 3.i有值,j空; 】的最大相似度。

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,m,f,g;
char sa[3100],sb[3100];
int a[3100],b[3100],mp[6][6];
int A[3100][3100],B[3100][3100],C[3100][3100];
inline int Max(int x,int y){return x>y ? x:y;}
int main()
{
    scanf("%s%s",sa+1,sb+1);
    n=strlen(sa+1); m=strlen(sb+1);
    for(int i=1;i<=n;++i)
    {
        switch(sa[i])
        {
            case 'A':a[i]=1; break;
            case 'T':a[i]=2; break;
            case 'G':a[i]=3; break;
            case 'C':a[i]=4; break;
        }
    }
    for(int i=1;i<=m;++i)
    {
        switch(sb[i])
        {
            case 'A':b[i]=1; break;
            case 'T':b[i]=2; break;
            case 'G':b[i]=3; break;
            case 'C':b[i]=4; break;
        }
    }
    for(int i=1;i<=4;++i) for(int j=1;j<=4;++j) scanf("%d",&mp[i][j]);
    scanf("%d%d",&f,&g);
    memset(A,0xef,sizeof A); memset(B,0xef,sizeof B); memset(C,0xef,sizeof C);
    A[0][0]=0;
    for(int i=0;i<=n;++i)
        for(int j=0;j<=m;++j)
        {
            if(i&&j) A[i][j]=Max(A[i-1][j-1],Max(B[i-1][j-1],C[i-1][j-1]))+mp[a[i]][b[j]];
            if(j) B[i][j]=Max(B[i][j-1]-g,Max(A[i][j-1],C[i][j-1])-f);
            if(i) C[i][j]=Max(C[i-1][j]-g,Max(A[i-1][j],B[i-1][j])-f);
        }
    printf("%d",Max(A[n][m],Max(B[n][m],C[n][m])));
    return 0;
}

发表评论

邮箱地址不会被公开。 必填项已用*标注