链接http://www.luogu.org/problem/show?pid=1140
题意：给你两个基因，每个基因可以两两对应，也可以一个对应空。不同的对应会得到不同的数字，求最大的对应和是多少
解析：dp。三个dp转移方程
1.dp[i][j] = dp[i - 1][j - 1] + match(a[i],b[j])注意此处不是max。
2.dp[i][j] = max(dp[i][j],dp[i - 1][j] + mapp[match(a[i])][4])第i个的对应为空
3.dp[i][j] = max(dp[i][j],dp[i][j - 1] + mapp[4][match(b[j])])第j个对应为空。
需要进行边界处理，先把i = 0和j = 0全都对应为空的处理好、
两个程序、
#include <iostream> #include <cstdio> #include <cstring> #include <sstream> #include <string> #include <algorithm> #include <list> #include <map> #include <vector> #include <queue> #include <stack> #include <cmath> #include <cstdlib> using namespace std; int mapp[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,-1000000000}}; char a[105],b[105]; int dp[105][105]; int match(char c) { if(c == 'A') return 0; if(c == 'C') return 1; if(c == 'G') return 2; if(c == 'T') return 3; return 4; } int main() { // freopen("in.txt","r",stdin); int n,m; scanf("%d%s",&n,a + 1); scanf("%d%s",&m,b + 1); for(int i = 1; i <= n; i ++) { dp[i][0] = dp[i - 1][0] + mapp[match(a[i])][4];//边界处理，此处的值是与后面的处理不一样的。这种边界不能取最大值，因为它本身是没有值的，就是不是从上衣个状态转移过来的。 //如果非得要合并在一起，需要把dp初始值设为无限小。 } for(int i = 1; i <= m; i ++) { dp[0][i] = dp[0][i - 1] + mapp[4][match(b[i])]; } for(int i = 1; i <= n; i ++) { for(int j = 1; j <= m; j ++) { dp[i][j] =dp[i - 1][j - 1] + mapp[match(a[i])][match(b[j])]; dp[i][j] = max(dp[i][j],dp[i - 1][j] + mapp[match(a[i])][4]); dp[i][j] = max(dp[i][j],dp[i][j - 1] + mapp[4][match(b[j])]); } } cout<<dp[n][m] <<endl; return 0; } #include <iostream> #include <cstdio> #include <cstring> #include <sstream> #include <string> #include <algorithm> #include <list> #include <map> #include <vector> #include <queue> #include <stack> #include <cmath> #include <cstdlib> using namespace std; int mapp[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,-1000000000}}; char a[105],b[105]; int dp[105][105]; int match(char c) { if(c == 'A') return 0; if(c == 'C') return 1; if(c == 'G') return 2; if(c == 'T') return 3; return 4; } int main() { //freopen("in.txt","r",stdin); int n,m; scanf("%d%s",&n,a + 1); scanf("%d%s",&m,b + 1); for(int i = 0; i <= n; i ++) { for(int j = 0; j <= m; j ++) { dp[i][j] = -1000000000; if(i == 0 && j == 0) { dp[0][0] = 0; continue; } if(i !=0 && j != 0) dp[i][j] =dp[i - 1][j - 1] + mapp[match(a[i])][match(b[j])]; if(i != 0) dp[i][j] = max(dp[i][j],dp[i - 1][j] + mapp[match(a[i])][4]); if(j != 0) dp[i][j] = max(dp[i][j],dp[i][j - 1] + mapp[4][match(b[j])]); } } cout<<dp[n][m] <<endl; return 0; }
