F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister
Problem 5107. -- [CodePlus2017]找爸爸

5107: [CodePlus2017]找爸爸

Time Limit: 10 Sec  Memory Limit: 512 MB
Submit: 273  Solved: 172
[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

Sample Output

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

[Submit][Status][Discuss]

HOME Back