[[原文:http://poj.org/problem?id=1080]]
----
''時間制限'':1000ミリ秒
''メモリ制限'':10000KB
&br;

*問題 [#ua5a176c]
２つのDNAデータが文字列として与えられる。
対応表(原文参照)に従って二つのDNAデータの適合度を算出せよ。

DNAデータは２つで各々1行ずつ与えられる。
DNAを表す各文字を一列ずつ比較してその合計として適合度が算出される。

| | A| C| G| T| -|
|A| 5|-1|-2|-1|-3|
|C|-1| 5|-3|-2|-4|
|G|-2|-3| 5|-2|-2|
|T|-1|-2|-2| 5|-1|
|-|-3|-4|-2|-1| *|



二つのDNAデータは長さが違うことがあり比較するときDNAの間に-を挟んでもよい。
両方のDNAデータに-を0個以上挟みDNAスコアーを最高にする組み合わせを探しそのスコアが答えとなる。

AGTGATGとGTTAGというデータを比較する場合。
 AGTGATG
 GTTAG--(-は長さ合わせのために挿入された)

1列目のAとGが比較され-2
2列目のGとTが比較され-2
3列目のTとTが比較され5
4列目のGとAが比較され-2
5列目のAとGが比較され5
6列目のTと-が比較され-1
7列目のGと-が比較され-2
で合計スコアは -2-2+5-2+5-1-2=1となるが。


これを
 AGTGATG 
 -GTTA-G 
上記のように-を入れると。

スコア算出の対応表より
1列目のAと-が比較され-3
2列目のGとGが比較され5
3列目のTとTが比較され5
4列目のGとTが比較され-2
5列目のAとAが比較され5
6列目のTと-が比較され-1
7列目のGとGが比較され5

合計スコアは-3+5+5+-2+5+-1+5＝14でこの-の入れ方が最もスコアが高いので
　AGTGATG 
　-GTTA-G が最高スコアを導く組み合わせで答えは14となる。


*入力 [#b262159f]
最初にデータセットの数Tが与えられる。
一つのデータセットは２行一組でDNAデータが与えられる。

一本目のDNAデータの長さ　一本目のDNAデータの文字列
二本目のDNAデータの長さ　二本目のDNAデータの文字列
という形式になっている。
DNAの長さは101を超えないと仮定してよい。

*出力 [#d1ef3e86]
各データセットにたいして最高のスコアを1行に一つ算出せよ。

*入力の例 [#m5eae7ff]
2 
7 AGTGATG 
5 GTTAG 
7 AGCTATT 
9 AGCTTTAAA 

*出力の例 [#r8be8846]
14
21

*出典 [#p8da5a11]
Taejon 2001