問題描述：
給出兩個(gè)串，對(duì)應(yīng)字母有權(quán)值，可以錯(cuò)位安排，使得最后總權(quán)和最大。
解題思路：
首先定義:
rt[a][b] 表示字符a和字符b配對(duì)時(shí)的權(quán)值
dp[i][j] 表示第一個(gè)串到i和第二個(gè)串到j(luò)兩個(gè)子串所組合出的最大權(quán)和為dp[i][j];
1)如果第i個(gè)字符和第j個(gè)字符配對(duì)，那么dp[i][j] = dp[i-1][j-1] + rt[str1[i]][str2[j]];
2)如果第一個(gè)串的第i個(gè)字符和'-'配對(duì), 那么dp[i][j] = dp[i-1][j] + rt[str1[i]]['-'];
3)如果第二個(gè)串的第j個(gè)字符和'-'配對(duì),那么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] ]);
}
}