1 #include <cstdio> 2 #include <cstring> 3 #include <cstdlib> 4 #include <map> 5 #include <iostream> 6 using namespace std; 7  8 #define MAXN 205 9 #define INF -9999910 #define TOKEN ‘-‘11 12 char r[MAXN], l[MAXN];13 int dp[MAXN][MAXN];14 int t, n, rn, ln;15 map<char, int> m;16 17 int mmap[5][5] = {18     {5, -1, -2, -1, -3},19     {-1, 5, -3, -2, -4},20     {-2, -3, 5, -2, -2},21     {-1, -2, -2, 5, -1},22     {-3, -4, -2, -1, 0}23 };24 25 int getmax(int a, int b) {26     return a>b ? a:b;27 }28 29 void init() {30     m[‘A‘] = 0;31     m[‘C‘] = 1;32     m[‘G‘] = 2;33     m[‘T‘] = 3;34     m[TOKEN] = 4;35 }36 37 int main() {38     int i, j, k, tmp, mmax;39     init();40 41 #ifndef ONLINE_JUDGE42     freopen("data.in", "r", stdin);43     freopen("data.out", "w", stdout);44 #endif45 46     scanf("%d", &t);47     while (t--) {48         scanf("%d %s", &rn, r);49         scanf("%d %s", &ln, l);50         dp[rn][ln] = 0;51         for (i=rn-1; i>=0; --i) {52             dp[i][ln] = dp[i+1][ln] + mmap[m[r[i]]][4];53         }54         for (j=ln-1; j>=0; --j) {55             dp[rn][j] = dp[rn][j+1] + mmap[4][m[l[j]]];56         }57         for (i=rn-1; i>=0; --i) {58             for (j=ln-1; j>=0; --j) {59                 mmax = INF;60                 if (r[i] == l[j])61                     mmax = getmax(mmax, mmap[m[r[i]]][m[l[j]]]+dp[i+1][j+1]);62                 else {63                     mmax = getmax(mmax, mmap[m[r[i]]][4]+dp[i+1][j]);64                     mmax = getmax(mmax, mmap[m[l[j]]][4]+dp[i][j+1]);65                     mmax = getmax(mmax, mmap[m[r[i]]][m[l[j]]]+dp[i+1][j+1]);66                 }67                 dp[i][j] = mmax;68             }69         }70         printf("%d\n", dp[0][0]);71     }72 73     return 0;74 }