#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 阅读(153)
评论(0) 编辑 收藏 引用 所属分类:
动态规划