题目：http://poj.org/problem?id=1080
题意：比较两个基因序列，测定它们的相似度，将两个基因排成直线，如果需要的话插入空格，使基因的长度相等，然后根据那个表格计算出相似度。
题解：
考虑f[i][j]：
① s1取第i个，s2取第j个， f[i][j] = f[i-1][j-1]+value[m(s1[i])][m(s2[j])];
② s1取第i个，s2用’-’， f[i][j] = f[i][j-1]+value[m(s1[i])][m(‘-’)];
③ s1用’-’，s2取第j个， f[i][j] = f[i-1][j]+value[m(‘-’)][m(s2[j])];
f[i][j] 为三者中最大者
考虑边界条件，即i或j为0的情况：
① 当i=j=0时，根据f[1][1] = f[0][0]+value[m(s1[i])][m(s2[j])],有f[0][0] = 0;
② 当i=0时，用f[0][j] = f[0][j-1]+ value[m(‘-’)][m(s2[j])]计算
③ 当j=0时，用f[i][0] = f[i-1][0]+ value[m(s1[i])][m(‘-’)]计算
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 6 int mmax(int a,int b,int c) 7 { 8 if(a>=b&&a>=c) 9 return a; 10 if(b>=a&&b>=c) 11 return b; 12 if(c>=a&&c>=b) 13 return c; 14 } 15 int f[5][5]={5,-1,-2,-1,-3, 16 -1,5,-3,-2,-4, 17 -2,-3,5,-2,-2, 18 -1,-2,-2,5,-1, 19 -3,-4,-2,-1,0 20 }; 21 22 int tran(char ch) 23 { 24 switch(ch) 25 { 26 case 'A':return 0; break; 27 case 'C':return 1; break; 28 case 'G':return 2; break; 29 case 'T':return 3; break; 30 case '-':return 4; 31 } 32 } 33 int d[110][110]; 34 int main() 35 { 36 int t,i,j,m,n; 37 char a[110],b[110]; 38 cin>>t; 39 while(t--) 40 { 41 memset(d,0,sizeof(d)); 42 cin>>m; getchar(); 43 cin>>a; 44 cin>>n; getchar(); 45 cin>>b; 46 d[0][0]=0; 47 for(j=1; j<=n; j++) 48 d[0][j]=f[tran('-')][tran(b[j-1])]+d[0][j-1];//这里刚开始求成了最大的，其实应该是每一个的- 与 49 //每一个的字符串匹配后的值， 而后面循环里的每一个d【i】[j]实际都有相同的字符，不足的是- 补全的。 50 51 for(i=1; i<=m; i++) 52 d[i][0]=f[tran(a[i-1])][tran('-')]+d[i-1][0]; 53 for(i=1; i<=m; i++) 54 for(j=1; j<=n; j++) 55 { 56 d[i][j]=mmax(f[tran(a[i-1])][tran(b[j-1])]+d[i-1][j-1],f[tran('-')][tran(b[j-1])]+d[i][j-1], 57 f[tran(a[i-1])][tran('-')]+d[i-1][j]);// 因为输入的原因，d 和 a. b 相差 一 58 } 59 cout<<d[m][n]<<endl; 60 } 61 return 0; 62 }