[CodePlus2017]找爸爸
Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 128 Solved: 87
[Submit][Status][Discuss]
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序列的最大相似程度。
Input
输入第1行一个字符串,表示小A的DNA序列。
输入第2行一个字符串,表示小B的DNA序列。
接下来4行,每行4个整数,用空格隔开,表示d数组,
具体顺序如下所示。
d(A,A)d(A,T)d(A,G)d(A,C)
d(T,A)d(T,T)d(T,G)d(T,C)
d(G,A)d(G,T)d(G,G)d(G,C)
d(C,A)d(C,T)d(C,G)d(C,C)
最后一行两个用空格隔开的正整数A,B,意义如题中所述。
对于所有测试点
有0<B<A≤1000,-1000≤d(x,y)≤1000,d(x,y)=d(y,x),
序列只包含{A,T,G,C}四种字符。
N+M<=3000
Output
输出共一行,表示两个序列的最大相似程度
Sample Input
ATGG
ATCC
5 -4 -4 -4
-4 5 -4 -4
-4 -4 5 -4
-4 -4 -4 5
2 1
ATCC
5 -4 -4 -4
-4 5 -4 -4
-4 -4 5 -4
-4 -4 -4 5
2 1
Sample Output
4
首先,将序列补成如下形式("-"代表空格)
ATGG--
AT--CC
然后所有d(x,y)的和为d(A,A)+d(T,T)=10所有极长连续空格段的相似程度之和为g(2)+g(2)=-6总和为4,可以验证
,这是相似程度最大的情况。
首先,将序列补成如下形式("-"代表空格)
ATGG--
AT--CC
然后所有d(x,y)的和为d(A,A)+d(T,T)=10所有极长连续空格段的相似程度之和为g(2)+g(2)=-6总和为4,可以验证
,这是相似程度最大的情况。
HINT
来自 CodePlus 2017 11 月赛,清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。
Credit:idea/邢健开 命题/邢健开 验题/陈宇
Git Repo:https://git.thusaac.org/publish/CodePlus201711
本次比赛的官方网址:cp.thusaac.org
感谢腾讯公司对此次比赛的支持。
Source
题解:dp,f[i][j][k][p]表示A串到了第i位,B串到了第j位,A串最后是否为空格,B串最后是否为空格
因为是一次函数。
1 #include<cstring> 2 #include<cmath> 3 #include<algorithm> 4 #include<iostream> 5 #include<cstdio> 6 7 #define inf 1000000007 8 #define ll long long 9 using namespace std; 10 inline int read() 11 { 12 int x=0,f=1;char ch=getchar(); 13 while(ch>'9'||ch<'0'){if (ch=='-') f=-1;ch=getchar();} 14 while(ch<='9'&&ch>='0'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();} 15 return x*f; 16 } 17 18 int n,m,d[5][5],dp[3005][3005][2][2],A,B; 19 char s1[3005],s2[3005]; 20 21 inline int D(char ch) 22 { 23 if (ch=='A') return 1; 24 else if (ch=='T') return 2; 25 else if (ch=='G') return 3; 26 else return 4; 27 } 28 int main() 29 { 30 scanf("%s%s",s1+1,s2+1); 31 n=strlen(s1+1);m=strlen(s2+1); 32 for (int i=1;i<=4;i++)for (int j=1;j<=4;j++) d[i][j]=read(); 33 A=read();B=read(); 34 for (int i=0;i<=n;i++) 35 for (int j=0;j<=m;j++) 36 for (int x1=0;x1<2;x1++) 37 for (int x2=0;x2<2;x2++) 38 dp[i][j][x1][x2]=-inf; 39 40 dp[0][0][1][1]=0;dp[1][0][1][0]=dp[0][1][0][1]=-A; 41 for (int i=1;i<=n;i++) 42 for (int j=1;j<=m;j++) 43 { 44 int x=D(s1[i]),y=D(s2[j]); 45 for (int x1=0;x1<2;x1++) 46 for (int x2=0;x2<2;x2++) 47 { 48 if (!x1&&!x2) continue; 49 dp[i][j][1][1]=max(dp[i-1][j-1][x1][x2]+d[x][y],dp[i][j][1][1]); 50 dp[i][j][1][0]=max(dp[i-1][j][x1][x2]-((x2)?A:B),dp[i][j][1][0]); 51 dp[i][j][0][1]=max(dp[i][j-1][x1][x2]-((x1)?A:B),dp[i][j][0][1]); 52 } 53 } 54 55 printf("%d",max(dp[n][m][1][1],max(dp[n][m][1][0],dp[n][m][0][1]))); 56 }