TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4336
  • 题目
  • P4336「CodePlus 2017 11 月赛」找爸爸
    限制 : 时间限制 : - MS   空间限制 : - KB
    评测说明 : 内存限制:512 MiB 时间限制:1000 ms
    问题描述

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

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

    1. 给出两个 DNA 序列,第一个长度为 n,第二个长度为 m。
    2. 在两个序列的任意位置插入任意多的空格,使得两个字符串长度相同。
    3. 逐位进行匹配,如果两个序列相同位置上的字符都不是空格,假设第一个是 x,第二个是 yyy,那么他们的相似程度由 d(x,y) 定义。对于两个序列中任意一段极长的长度为 kkk 的连续空格,我们定义这段空格的相似程度为 g(k)=−A−B(k−1)。

    那么最终两个序列的相似程度就是所有的 d(x,y) 加上所有的极长空格段的相似程度之和。

    现在小 A 通过某种奥妙重重的方式得到了小 B 的 DNA 序列中的一段,他想请你帮他算一下小 A 的 DNA 序列和小 B 的 DNA 序列的最大相似程度。

    输入格式

    输入第 111 行一个字符串,表示小 A 的 DNA 序列。

    输入第 222 行一个字符串,表示小 B 的 DNA 序列。

    接下来 444 行,每行 444 个整数,用空格隔开,表示 ddd 数组,具体顺序如下所示。

    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,意义如题中所述。

    输出格式

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

    样例输入

    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<A≤1000, −1000≤d(x,y)≤1000, d(x,y)=d(y,x)  0< B<A

    序列只包含 {A,T,G,C}四种字符。

     

    n+m≤3000