P4059 [Code+#1]找爸爸

    • 152通过
    • 449提交
  • 题目提供者 Xeonacid
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 递推 O2优化
  • 难度 提高+/省选-
  • 时空限制 1000ms / 512MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

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

    输出格式:

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

    输入输出样例

    输入样例#1: 复制
    ATGG
    ATCC
    5 -4 -4 -4 
    -4 5 -4 -4 
    -4 -4 5 -4 
    -4 -4 -4 5 
    2 1
    输出样例#1: 复制
    4

    说明

    样例解释

    首先,将序列补成如下形式("-"代表空格)

    ATGG--
    AT--CC

    然后所有$d(x,y)$的和为$d(A,A)+d(T,T)=10$

    所有极长连续空格段的相似程度之和为$g(2)+g(2)=-6$

    总和为$4$,可以验证,这是相似程度最大的情况。

    对于所有测试点,有$0< B<A \le 1000, -1000\le d(x,y)\le 1000,d(x,y)=d(y,x)$,序列只包含${A,T,G,C}$四种字符。

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

    Credit:idea/卢政荣 命题/卢政荣 验题/何昊天

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

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

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。