网站页面
当前课程
成员
General
主题 1
主题 2
主题 4
主题 5
主题 6
主题 7
主题 8
主题 9
主题 10
主题 11
主题 12
主题 13
主题 14
主题 15
主题 16
主题 17
主题 18
主题 19
主题 20
DNA重组
成绩 | 0 | 开启时间 | 2013年02月21日 星期四 23:02 |
折扣 | 0.8 | 折扣时间 | 2013年02月28日 星期四 23:02 |
允许迟交 | 是 | 关闭时间 | 2013年02月28日 星期四 23:02 |
输入文件 | dna.in | 输出文件 | dna.out |
【问题描述】
在24世纪,Z国将成为科技最发达的国家,特别是在生物工程领域,他们拥有这样的高新科技,比如使用基因剪,可以将基因链从任意一处断开,而使用基因胶,又可以将任意的基因片断粘到一个集成链上。我们知道,DNA是由一个核苷酸聚合链构成的,一共有4种类型的核苷酸,分别为"A","T","C","G"。
有一次,Z国的研究人员从一些原始的有机组织中提取出了一条DNA链,他们的任务是通过对旧的DNA进行重组,进而生成一条新的DNA链。他们投资了一个计划,用如下的方式使用基因剪和基因胶。
首先,他们将DNA链在某些连接点处断开,这样整个链就会就变成一些DNA片断,然后他们再决定是保留还是丢弃这些片断,如果保留这些片断,他们将利用基因胶把它们粘成一条新链,注意,粘的过程中不能打乱这些片断原来的顺序。在整个过程中他们不得不非常小心地确定这些片断的去留。
当然了,做这些操作是需要花费代价的,每一个“剪开”的操作代价为1,每一个“粘合”操作花费代价也为1。请你写一个程序计算:如果存在一种方式生成一个新的DNA链,那么所需操作的最小代价是多少?
请看下面的例子:
旧的DNA:A---T---A---C---C---G
剪开后: A
T A---C C---G
保留: T
C---G
新的DNA链: T---C---G
花费代价:4
【输入格式】
输入文件第一行有一个正整数T,表示接下来测试数据的个数。每一个测试数据包含两行,每行一个字符串,第一个字符串表示旧的DNA链,第二行为新的DNA链。每个字符串都由"A","T","C"和"G"组成,每一个字符串的长度均不超过3000。
【输出格式】
对于每一个测试数据,输出其最小花费,如果没办法生成新的DNA链,则输出“-1”。
【样例】
dna.in
2
ATACCG
TCG
ATACCG
CTG
dna.out
4
-1