最长公共子序列的变形题，算法导论公共子序列后的练习题有题是类似的
注意在公共子序列中要判断a[i]和b[j]相等，而此题是考虑相似，不要求相等
1 #include <iostream> 2 #include <vector> 3 #include <algorithm> 4 #include <cstdio> 5 #include <cstring> 6 #include <string> 7 #include <map> 8 9 #define MAX 100 + 5 10 using namespace std; 11 12 //dp[i][j]表示字符串a以a[i]结尾，字符串b以b[j]结尾的最大相似度 13 int dp[MAX][MAX]; 14 15 int score[5][5]={ 16 {5,-1,-2,-1,-3}, 17 {-1,5,-3,-2,-4}, 18 {-2,-3,5,-2,-2}, 19 {-1,-2,-2,5,-1}, 20 {-3,-4,-2,-1,0} 21 }; 22 23 int main(){ 24 map<char,int> table; 25 table['A'] = 0;table['C'] = 1;table['G'] = 2; 26 table['T'] = 3;table['-'] = 4; 27 int T; 28 cin >> T; 29 while(T--){ 30 int na,nb; 31 string stra,strb; 32 cin >> na>>stra >> nb>>strb; 33 memset(dp,0,sizeof(dp)); 34 //注意边界条件 35 for(int i = 1; i <= na; i ++ ) dp[i][0] = dp[i-1][0] + score[ table[ stra[i-1] ] ][ table[ '-' ] ]; 36 for(int i = 1; i <= nb; i ++ ) dp[0][i] = dp[0][i-1] + score[ table['-'] ][ table[ strb[i-1] ] ]; 37 38 for(int i = 1 ; i <= na; i ++ ){ 39 for(int j = 1; j <= nb; j ++){ 40 dp[i][j]= max(dp[i- 1 ][j -1 ] + score[ table[ stra[i-1] ] ][ table[ strb[j-1] ]], 41 max(dp[i- 1 ][j] + score[ table[ stra[i-1] ]][ table[ '-' ]], dp[i][j-1] + score[ table[ '-' ]][ table[ strb[j-1] ]]) ); 42 } 43 } 44 cout<<dp[na][nb]<<endl; 45 46 } 47 48 49 return 0; 50 }