[CodePlus2017]找爸爸

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

输入第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

输出共一行，表示两个序列的最大相似程度


			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，可以验证

，这是相似程度最大的情况。

来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会荣誉出品。

Credit：idea/邢健开　命题/邢健开　验题/陈宇

Git Repo：https://git.thusaac.org/publish/CodePlus201711

本次比赛的官方网址：cp.thusaac.org

感谢腾讯公司对此次比赛的支持。

#5107. [CodePlus2017]找爸爸