小 A 最近一直在找自己的爸爸,用什么办法呢,就是 DNA 比对。
小 A 有一套自己的 DNA 序列比较方法,其最终目标是最大化两个 DNA 序列的相似程度,具体步骤如下:
那么最终两个序列的相似程度就是所有的 d(x,y) 加上所有的极长空格段的相似程度之和。
现在小 A 通过某种奥妙重重的方式得到了小 B 的 DNA 序列中的一段,他想请你帮他算一下小 A 的 DNA 序列和小 B 的 DNA 序列的最大相似程度。
输入第 1 行一个字符串,表示小 A 的 DNA 序列。
输入第2 行一个字符串,表示小 B 的 DNA 序列。
接下来 4 行,每行 4 个整数,用空格隔开,表示d 数组,具体顺序如下所示。
最后一行两个用空格隔开的正整数 A,B,意义如题中所述。
输出共一行,表示两个序列的最大相似程度。
ATGG ATCC 5 -4 -4 -4 -4 5 -4 -4 -4 -4 5 -4 -4 -4 -4 5 2 1
4
首先,将序列补成如下形式(-
代表空格)
ATGG-- AT--CC
然后所有 d(x,y) 的和为 d(A,A)+d(T,T)=10,所有极长连续空格段的相似程度之和为 g(2)+g(2)=-6。总和为 4,可以验证,这是相似程度最大的情况。
对于所有测试点,有 0< B, -1000 \le d(x,y) \le 1000,d(x,y)=d(y,x) ,序列只包含 \{\text{A},\text{T},\text{G},\text{C}\} 四种字符。
CodePlus 2017 11 月赛