万里ACM discuss3

Description

小 A 最近一直在找自己的爸爸，用什么办法呢，就是 DNA 比对。

小 A 有一套自己的 DNA 序列比较方法，其最终目标是最大化两个 DNA 序列的相似程度，具体步骤如下：

给出两个 DNA 序列，第一个长度为 $n$ ，第二个长度为 $m$ 。
在两个序列的任意位置插入任意多的空格，使得两个字符串长度相同。
逐位进行匹配，如果两个序列相同位置上的字符都不是空格，假设第一个是 $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$ ，意义如题中所述。

Output

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

Sample Input Copy

ATGG
ATCC
5 -4 -4 -4
-4 5 -4 -4
-4 -4 5 -4
-4 -4 -4 5
2 1

Sample Output Copy

HINT

对于所有测试点，有 $0，序列只包含 {A,T,G,C}\{\text{A},\text{T},\text{G},\text{C}\} 四种字符。$

测试点编号	$n + m$ 的范围	特殊约定
1	$n = m = 1$	无特殊要求
2	$\leq 15$
3	$\leq 300$
4	$\leq 300$
5	$\leq 3000$	序列中只包含一种字符
6		无特殊要求
7
8
9
10

来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会荣誉出品。
Credit：idea/邢健开　命题/邢健开　验题/陈宇
Git Repo：https://git.thusaac.org/publish/CodePlus201711
感谢腾讯公司对此次比赛的支持。

Source/Category

LibreOJ