TG
5 GTTAG
7 AGCTATT
9 AGCTTTAAA
Sample Output
14
21
论LCS的不死性。LCS改编版。
#include
#include
#include
#include
#include
using namespace std; char s1[110],s2[110]; int dp[110][110]; int t,len1,len2; int mp[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 get(char c) { switch(c) { case 'A':return 0; case 'C':return 1; case 'G':return 2; case 'T':return 3; case '-':return 4; } } int main() { scanf("%d",&t); while(t--) { getchar(); scanf("%d%s",&len1,s1); scanf("%d%s",&len2,s2); memset(dp,0,sizeof(dp)); for(int i=1;i<=len1;i++) dp[i][0]=dp[i-1][0]+mp[get(s1[i-1])][get('-')]; for(int j=1;j<=len2;j++) dp[0][j]=dp[0][j-1]+mp[get('-')][get(s2[j-1])]; for(int i=1;i<=len1;i++) { for(int j=1;j<=len2;j++) { int t1=dp[i-1][j]+mp[get(s1[i-1])][get('-')]; int t2=dp[i][j-1]+mp[get('-')][get(s2[j-1])]; int t3=dp[i-1][j-1]+mp[get(s1[i-1])][get(s2[j-1])]; dp[i][j]=max(t1,max(t2,t3)); } } printf("%d\n",dp[len1][len2]); } return 0; }