#include?
<
stdio.h
>
int
?m,?n;
char
?a[
110
],?b[
110
];
int
??result[
110
][
110
];
int
??value[
5
][
5
]
=
?
{???
{?
5
,?
-
1
,?
-
2
,?
-
1
,?
-
3
?}
,
??????????????????????
{?
-
1
,?
5
,?
-
3
,?
-
2
,?
-
4
?}
,
??????????????????????
{?
-
2
,?
-
3
,?
5
,?
-
2
,?
-
2
?}
,
??????????????????????
{?
-
1
,?
-
2
,?
-
2
,?
5
,?
-
1
?}
,
??????????????????????
{?
-
3
,?
-
4
,?
-
2
,?
-
1
,?
-
1000
}
?}
;
int
?getid(?
char
?ch?)
{
????
switch
(?ch?)
????
{
????????
case
?
'
A
'
:??
return
?
0
;
????????
case
?
'
C
'
:??
return
?
1
;
????????
case
?
'
G
'
:??
return
?
2
;
????????
case
?
'
T
'
:??
return
?
3
;
????????
case
?
'
-
'
:??
return
?
4
;
????}
????
????
return
?
-
1
;
}
int
?solve()
{????
????result[
0
][
0
]
=
?
0
;
????
for
(?
int
?i
=
?
0
;?i
<
?m;?
++
i?)?result[i
+
?
1
][
0
]
=
?result[i][
0
]
+
?value[?getid(?a[i]?)?][
4
];
????
for
(?
int
?i
=
?
0
;?i
<
?n;?
++
i?)?result[
0
][i
+
?
1
]
=
?result[
0
][i]
+
?value[
4
][?getid(?b[i]?)?];
????
for
(?
int
?i
=
?
0
;?i
<
?m;?
++
i?)
????????
for
(?
int
?j
=
?
0
;?j
<
?n;?
++
j?)
????????
{
????????????result[i
+
?
1
][j
+
?
1
]
=
?result[i][j]
+
?value[?getid(?a[i]?)?][?getid(?b[j]?)?];
????????????
????????????
if
(?result[i
+
?
1
][j]
+
?value[
4
][?getid(?b[j]?)?]?
>
?result[i
+
1
][j
+
1
]?)
????????????result[i
+
1
][j
+
1
]
=
?result[i
+
?
1
][j]
+
?value[
4
][?getid(?b[j]?)?];
????????????
????????????
if
(?result[i][j
+
?
1
]
+
?value[?getid(?a[i]?)?][
4
]?
>
?result[i
+
1
][j
+
1
]?)
????????????result[i
+
1
][j
+
1
]
=
?result[i][j
+
?
1
]
+
?value[?getid(?a[i]?)?][
4
];
????????}
????
????
return
?result[m][n];
}
int
?main()
{
????
int
?test;
????scanf(
"
%d
"
,
&
test);
????
????
while
(?test
--
?)
????
{
????????scanf(
"
%d
"
,
&
m);?scanf(
"
%s
"
,?a?);
????????scanf(
"
%d
"
,
&
n);?scanf(
"
%s
"
,?b?);
????????
????????printf(
"
%d\n
"
,?solve()?);
????}
????
return
?
0
;
}
posted on 2008-10-28 18:34
Darren 閱讀(194)
評論(0) 編輯 收藏 引用 所屬分類:
動態規劃