HDU 1080（dp46)

#include<stdio.h> #include<string.h> #include<iostream> #include<algorithm> using namespace std; int dp[1005][1005]; char str1[1005],str2[1005]; int map[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 exchange(char a) { int i; if(a=='A') i=0; else if(a=='C') i=1; else if(a=='G') i=2; else if(a=='T') i=3; else i=4; return i; } int Texchange(char a,char b) { int x,y; x=exchange(a); y=exchange(b); return map[x][y]; } int main() { int i,j; int T; scanf("%d",&T); while(T--) { int len1,len2; scanf("%d",&len1); cin>>str1+1; scanf("%d",&len2); cin>>str2+1; memset(dp,0,sizeof(dp)); for(i=1;i<=len1;i++) dp[i][0]=dp[i-1][0]+Texchange(str1[i],'-'); for(i=1;i<=len2;i++) dp[0][i]=dp[0][i-1]+Texchange('-',str2[i]); for(i=1;i<=len1;i++) { for(j=1;j<=len2;j++) { dp[i][j]=max(dp[i-1][j-1]+Texchange(str1[i],str2[j]),max(dp[i-1][j]+Texchange(str1[i],'-'),dp[i][j-1]+Texchange('-',str2[j]))); } } printf("%d\n",dp[len1][len2]); } return 0; }