「CodePlus 2017 11月赛」找爸爸 - 类LCS | Bill Yang's Blog

「CodePlus 2017 11月赛」找爸爸 - 类LCS

题目大意

    小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序列的最大相似程度。


题目分析

简单动规,设$f[i,j,0/1/2]$分别表示匹配到第$(i,j)$位,字与字匹配,字与空格匹配,空格与字匹配的最大权值和。
注意细节蛮多的。


代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

inline const int Get_Int() {
int num=0,bj=1;
char x=getchar();
while(x<'0'||x>'9') {
if(x=='-')bj=-1;
x=getchar();
}
while(x>='0'&&x<='9') {
num=num*10+x-'0';
x=getchar();
}
return num*bj;
}

char s1[3005],s2[3005];
int n,m,M[205],A,B,a[5][5],f[3005][3005][3];

int main() {
M['A']=1,M['T']=2,M['G']=3,M['C']=4;
scanf("%s %s",s1+1,s2+1);
n=strlen(s1+1),m=strlen(s2+1);
for(int i=1; i<=4; i++)
for(int j=1; j<=4; j++)
a[i][j]=Get_Int();
A=Get_Int(),B=Get_Int();
for(int i=0; i<=n; i++)
for(int j=0; j<=m; j++)
f[i][j][0]=f[i][j][1]=f[i][j][2]=-INT_MAX/2;
f[0][0][0]=0;
for(int i=1; i<=n; i++) {
f[0][i][1]=max(max(f[0][i-1][0],f[0][i-1][2])-A,f[0][i-1][1]-B);
f[i][0][2]=max(max(f[i-1][0][0],f[i-1][0][1])-A,f[i-1][0][2]-B);
}
for(int i=1; i<=n; i++)
for(int j=1; j<=m; j++) {
f[i][j][0]=max(f[i-1][j-1][0],max(f[i-1][j-1][1],f[i-1][j-1][2]))+a[M[s1[i]]][M[s2[j]]];
f[i][j][1]=max(max(f[i][j-1][0],f[i][j-1][2])-A,f[i][j-1][1]-B);
f[i][j][2]=max(max(f[i-1][j][0],f[i-1][j][1])-A,f[i-1][j][2]-B);
}
printf("%d\n",max(f[n][m][0],max(f[n][m][1],f[n][m][2])));
return 0;
}
姥爷们赏瓶冰阔落吧~
0%