C - Human Gene Functions (1-12)

#include <iostream>
#include <algorithm>
#include <string>
#include <string.h>
using namespace std;

int score[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, 0
                  };

int change(char c) {
    if(c == 'A') return 0;
    if(c == 'C') return 1;
    if(c == 'G') return 2;
    if(c == 'T') return 3;
    if(c == ' ') return 4;
}

int dp[105][105];

void solve() {
    int n, m;
    string s, t;

    cin >> n >> s;
    cin >> m >> t;

    memset(dp, 0, sizeof(dp));

    for(int i = 1; i <= n; i++)
        dp[i][0] = dp[i-1][0] + score[change(s[i-1])][change(' ')];

    for(int j = 1; j <= m; j++)
        dp[0][j] = dp[0][j-1] + score[change(' ')][change(t[j-1])];

    for(int i = 1; i <= n; i++)
        for(int j = 1; j <= m; j++) {
            dp[i][j] = -1e9;
            dp[i][j] = max(dp[i][j], dp[i-1][j-1] + score[change(s[i-1])][change(t[j-1])]);
            dp[i][j] = max(dp[i][j], dp[i-1][j] + score[change(s[i-1])][change(' ')]);
            dp[i][j] = max(dp[i][j], dp[i][j-1] + score[change(t[j-1])][change(' ')]);
        }

    cout << dp[n][m] << '\n';
}

int main() {
    //freopen("C-HumanGeneFunctions.inp", "r", stdin);
    //freopen("C-HumanGeneFunctions.out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t; cin >> t;
    while(t--) {
        solve();
    }

    return 0;
}