Human Gene Functions
http://poj.org/problem?id=1080
题意：已知一个人类基因的积分表，给出两个字符串，计算这两个串的最大相似程度；
思路：最长公共子序列的变形，用score[][] 表示积分值，dp[i][j]表示字符串s1[1,2,,,i]和s2[1,2,,,j]的分值，对一个dp[i][j],有三种可能：
> s1取第i个字符，s2取‘-’时，dp[i][j] = dp[i-1][j] + score[s1[i]][0];
>s1取‘-’,s2取第j个字符时，dp[i][j] = dp[i][j-1] + score[0][s2[j]];
>s1取第i个字符，s2取第j个字符时，dp[i][j] = dp[i-1][j-1] + score[s1[i]][s2[j]];
取上述三个数的最大值即是dp[i][j];
注意初始化也与LCS不同，
dp[0][0] = 0;
当i= 0时，dp[0][j] = dp[0][j-1] + score[0][s2[j]];
当j = 0时，dp[i][0] = dp[i-1][0] + score[s1[i]][0];
1 #include<stdio.h> 2 #include<string.h> 3 4 int score[5][5] ={0,-3,-4,-2,-1, 5 -3,5,-1,-2,-1, 6 -4,-1,5,-3,-2, 7 -2,-2,-3,5,-2, 8 -1,-1,-2,-2,5,};//积分表 9 10 int change(char ch) 11 { 12 if(ch == 'A') 13 return 1; 14 else if(ch == 'C') 15 return 2; 16 else if(ch == 'G') 17 return 3; 18 else if(ch == 'T') 19 return 4; 20 } 21 22 int max(int a,int b,int c) 23 { 24 if(a >= b && a >= c) 25 return a; 26 if(b >= a && b >= c) 27 return b; 28 if(c >= a && c >= b) 29 return c; 30 } 31 32 int a[110],b[110],len1,len2,dp[110][110]; 33 char s1[110],s2[110]; 34 35 int main() 36 { 37 int test,i,j; 38 scanf("%d",&test); 39 while(test--) 40 { 41 memset(a,0,sizeof(a)); 42 memset(b,0,sizeof(b)); 43 44 scanf("%d %s",&len1,s1); 45 scanf("%d %s",&len2,s2); 46 47 for(i = 0; i < len1; i++) 48 a[i+1] = change(s1[i]); 49 for(i = 0; i < len2; i++) 50 b[i+1] = change(s2[i]); 51 52 //初始化 53 memset(dp,0,sizeof(dp)); 54 dp[0][0] = 0; 55 for(int i = 1; i <= len2; i++) 56 dp[0][i] = dp[0][i-1]+score[0][b[i]]; 57 for(int i = 1; i <= len1; i++) 58 dp[i][0] = dp[i-1][0]+score[a[i]][0]; 59 60 for(i = 1; i <= len1; i++) 61 { 62 for(j = 1; j <= len2; j++) 63 { 64 int tmp1 = dp[i-1][j]+score[a[i]][0];//s1取第i个字母，s2取‘-’； 65 int tmp2 = dp[i][j-1]+score[0][b[j]];//s1取‘-’，s2取第j个字母； 66 int tmp3 = dp[i-1][j-1]+score[a[i]][b[j]];//s1取第i个字母，s2取第j个字母； 67 int tmp = max(tmp1,tmp2,tmp3); 68 dp[i][j] += tmp; 69 } 70 } 71 printf("%d ",dp[len1][len2]); 72 } 73 return 0; 74 }