英雄哪里出來

問題描述：
給出兩個串，對應字母有權值，可以錯位安排，使得最后總權和最大。
解題思路：
首先定義:
rt[a][b]   表示字符a和字符b配對時的權值
dp[i][j] 表示第一個串到i和第二個串到j兩個子串所組合出的最大權和為dp[i][j];
1)如果第i個字符和第j個字符配對，那么dp[i][j] = dp[i-1][j-1] + rt[str1[i]][str2[j]];
2)如果第一個串的第i個字符和'-'配對, 那么dp[i][j] = dp[i-1][j] + rt[str1[i]]['-'];
3)如果第二個串的第j個字符和'-'配對,那么dp[i][j] = dp[i][j-1] + rt['-'][str2[j]];
于是dp[i][j] = max{ dp[i-1][j-1] + rt[str1[i]][str2[j]],   dp[i-1][j] + rt[str1[i]]['-'],  dp[i][j-1] + rt['-'][str2[j]] };

核心代碼：

#include <iostream>

using namespace std;

int dp[110][110];
char str[2][110];
int len[2];
int i, j;

int rt[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 num(char c){
    if(c == 'A')
        return 0;
    if(c == 'C')
        return 1;
    if(c == 'G')
        return 2;
    if(c == 'T')
        return 3;
    return 4;
}

int Max(int a, int b, int c){
    if(c > b) b = c;
    return a > b ? a : b;
}

int main()
{
    int t;
    scanf("%d", &t);
    while(t--){
        for(i = 0; i < 2; i++){
            scanf("%d", &len[i]);
            scanf("%s", &str[i][1]);
        }

        dp[0][0] = 0;
        for(i = 1; i <= len[0]; i++){
            dp[i][0] = dp[i-1][0] + rt[ num(str[0][i]) ][num('-')];
        }

        for(i = 1; i <= len[1]; i++){
            dp[0][i] = dp[0][i-1] + rt[ num('-') ][ num(str[1][i]) ];
        }

        for(i = 1; i <= len[0]; i++){
            for(j = 1; j <= len[1]; j++){
                dp[i][j] = Max(
                    dp[i-1][j-1] + rt[ num(str[0][i]) ][num(str[1][j])], 
                    dp[i-1][j] + rt[ num(str[0][i]) ][ num('-') ],
                    dp[i][j-1] + rt[ num('-') ][ num(str[1][j]) ]
                    );
            }
        }
        printf("%d\n", dp[ len[0] ][ len[1] ]);
    }
}