Pro.ID21631 TitleDNA recombination Title链接http://10.20.2.8/oj/exercise/problem?problem_id=21631 AC0 Submit0 Ratio- 时间&空间限制描述Country Z possesses the most high-tech in 24 century, especially in bioengineering area. They have such technology that when using gene-scissors, they could cut off a DNA chain from any conjunction, similarly, when using gene-gluewater, they could concatenate each pieces into an integrated chain. We know that DNA is made up with a polymeric chain of nucleotides. There are four kinds of nucleotides which are "A", "T", "C", "G". One time, researchers in Country Z extracted a DNA chain from some primitive organism. Their objective is to generate a new DNA chain with recombining the old one. They invested a plan by using their gene-scissors and gene-gluewater as follow. At first, they cut off the connections between some adjacent nucleotides. So the DNA chain is split into pieces of DNA fragment. Then they choose to reserve or discard these DNA fragments. For the fragments reserved, they use gene-gluewater to concatenate them into a new chain. Notice that one cannot disrupt the order of the fragments. What they can do is just to reconnect the joint between the adjacent reserved DNA fragments. So they have to carefully decide up which conjunction to be cut off and which fragments to be reserved. Also it takes some cost of doing these operations. Each "Cut-off operation" cost 1 unit, and each "Concatenate operation" cost 1 unit, too. Write a program to minimal the cost of generating the new DNA chain if there exists a way. Take the following example: Old DNA: A --- T --- A --- C --- C --- G Cut-off: A T A --- C C --- G Reserved: T C --- G Concatenated: T --- C --- G New DNA: T --- C --- G Cost: 4 输入The first line of the input is a positive integer T. T is the number of test cases followed. Each test case contains two strings in two lines, the first string is Old DNA chain, and the second is New DNA chain. Each string is made up with "A", "T", "C", and "G". And the length of string will be no more than 3000. 输出Description Country Z possesses the most high-tech in 24 century, especially in bioengineering area. They have such technology that when using gene-scissors, they could cut off a DNA chain from any conjunction, similarly, when using gene-gluewater, they could concatenate each pieces into an integrated chain. We know that DNA is made up with a polymeric chain of nucleotides. There are four kinds of nucleotides which are "A", "T", "C", "G". One time, researchers in Country Z extracted a DNA chain from some primitive organism. Their objective is to generate a new DNA chain with recombining the old one. They invested a plan by using their gene-scissors and gene-gluewater as follow. At first, they cut off the connections between some adjacent nucleotides. So the DNA chain is split into pieces of DNA fragment. Then they choose to reserve or discard these DNA fragments. For the fragments reserved, they use gene-gluewater to concatenate them into a new chain. Notice that one cannot disrupt the order of the fragments. What they can do is just to reconnect the joint between the adjacent reserved DNA fragments. So they have to carefully decide up which conjunction to be cut off and which fragments to be reserved. Also it takes some cost of doing these operations. Each "Cut-off operation" cost 1 unit, and each "Concatenate operation" cost 1 unit, too. Write a program to minimal the cost of generating the new DNA chain if there exists a way. Take the following example: Old DNA: A --- T --- A --- C --- C --- G Cut-off: A T A --- C C --- G Reserved: T C --- G Concatenated: T --- C --- G New DNA: T --- C --- G Cost: 4 Input The first line of the input is a positive integer T. T is the number of test cases followed. Each test case contains two strings in two lines, the first string is Old DNA chain, and the second is New DNA chain. Each string is made up with "A", "T", "C", and "G". And the length of string will be no more than 3000. Output For each test case, output the minimal cost. If there is no way in generating New DNA chain, output "-1" instead. Sample Input 2 Sample Output 4 Source 样例输入2 样例输出4 作者 |
|Archiver|手机版|小黑屋|同和创作矩阵
( 粤ICP备20019636号-1 )
GMT+8, 2025-2-3 12:03 , Processed in 0.015603 second(s), 14 queries .
Powered by Discuz! X3.4 Licensed
© 2001-2017 Comsenz Inc.
