题目内容

P1140

大意:给出两段碱基对序列,将他们对应起来,可以一对空,求最大相似度

解题思路

首先定义状态:f(i,j) 表示 a 基因的前 i 个碱基与 b 基因的前 j 个碱基对应起来能达到的最大相似度。

由于最后一对碱基只有三种可能:

  1. 一对二
  2. 一对空
  3. 空对二

所以可以很明显的得到状态转移方程:

f(i,j)=\max(f(i-1,j-1)+d(a_i,b_i),~f(i,j-1)+d(5,b_j),~f(i-1,j)+d(a_i,5))

这个方程的意义就是,如果最后一对碱基是一对二,那么从前一个状态出发,再加上两个对应的相似度,如果是一对空,那么就是从前一个出发,将一和空的相似度加上,空对二同理。

然后是先判边界:

f(i,0)=f(i-1,0)+d(i,5)\
f(0,i)=f(0,i-1)+d(5,i)

否则会 WA,由于状态是从前一个下标推过来的,所以一定要定义初始边界值,递推的时候从小到大。

代码:

#include <cstdio>

int d[6][6]={//对应的表
    {0,0,0,0,0,0},
    {0,5,-1,-2,-1,-3},
    {0,-1,5,-3,-2,-4},
    {0,-2,-3,5,-2,-2},
    {0,-1,-2,-2,5,-1},
    {0,-3,-4,-2,-1,0}
};


inline int max(int a,int b)
{
    return a>b?a:b;
}

inline int max(int a,int b,int c)
{
    return max(max(a,b),c);
}

int l1,l2;
char a[105],b[105];
int f[105][105];

int main()
{
    scanf("%d %s",&l1,a+1);
    scanf("%d %s",&l2,b+1);
    for(int i=1;i<=l1;i++)
    {
        a[i]=a[i]=='A'?1:a[i]=='C'?2:a[i]=='G'?3:4;//压行我最棒
        f[i][0]=f[i-1][0]+d[a[i]][5];//初始边界
    }
    for(int i=1;i<=l2;i++)
    {
        b[i]=b[i]=='A'?1:b[i]=='C'?2:b[i]=='G'?3:4;
        f[0][i]=f[0][i-1]+d[5][b[i]];//初始边界
    }
    for(int i=1;i<=l1;i++)
        for(int j=1;j<=l2;j++)
            f[i][j]=max(f[i-1][j]+d[a[i]][5],f[i][j-1]+d[5][b[j]],f[i-1][j-1]+d[a[i]][b[j]]);//超长的转移
    printf("%d\n",f[l1][l2]);
    return 0;
}
最后修改日期:2020年3月4日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。