2021057 2006-08-14 17:39:09 Accepted 1027 C++ 00:00.01 428K St.Crux 两个字符串si和sk，每个字符匹配都有一个权值，要求他们的最大匹配权值。 很久以前在论坛上看过介绍，说和求最长子序列十分类似，因此很快就联想到了dp:) 事实上，这个题和LCS......确实很相似。同样是用一个二维数组来表示si的前i个数与sk的前k个数（字符）匹配的最大值，同样在f(n, m)处得解。不同的是LCs求的是最大长度，而这个求的是最大值。 所以用从下向上递推的思想分析。比如si＝AT，sk＝TA。当A和T匹配后，显然有一种情况：f(2, 2) = f(1,1) + a[2][2]； 那么移一位如何？即把si的T移动到TA的后面，使A和TA匹配，得f(2, 2) = f(1, 2) + T与-的匹配值。同理可得其他情况，在这些情况中取最大值即可。 #include <cstdio>#include <string> int a[5][5] = { {5, -1, -2, -1, -3}, {-1, 5, -2, -3, -4}, {-2, -3, 5, -2, -2}, {-1, -2, -2, 5, -1}, {-3, -4, -2, -1, 0} }, b[101][101], s0[101], s1[101];int n, m, t, ans; int mx(int a, int b, int c){ if(a >= b && a >= c)  return a; if(b >= a && b >= c)  return b; if(c >= a && c >= b)  return c; else  return -99999999;} void read(){ char tc; int k; scanf("%d ", &n); for(k = 0; k < n; k ++) {    scanf("%c", &tc);  if(tc == 'A') s0[k] = 0;  if(tc == 'C') s0[k] = 1;  if(tc == 'G') s0[k] = 2;  if(tc == 'T') s0[k] = 3; } scanf("%d ", &m); for(k = 0; k < m; k ++) {  scanf("%c", &tc);  if(tc == 'A') s1[k] = 0;  if(tc == 'C') s1[k] = 1;  if(tc == 'G') s1[k] = 2;  if(tc == 'T') s1[k] = 3; }} void init(){ memset(b, 0, sizeof(b)); int i, sum = 0; for(i = 1; i <= n; i ++) {  sum += a[s0[i - 1]][4];  b[i][0] = sum; } sum = 0; for(i = 1; i <= m; i ++) {  sum += a[s1[i - 1]][4];  b[0][i] = sum; } ans = -99999999;} void dp(){ int i, k; for(i = 1; i <= n; i ++) {  for(k = 1; k <= m; k ++)  {   int ta = b[i - 1][k - 1] + a[s0[i - 1]][s1[k - 1]];   int tb = b[i][k - 1] + a[4][s1[k - 1]];   int tc = b[i - 1][k] + a[s0[i - 1]][4];   b[i][k] = mx(ta, tb, tc);  } } ans = b[n][m];} void ps(){ int i; for(i = 0; i < n; i ++) {  printf("%d ", s0[i]); } printf("\n"); for(i = 0; i < m; i ++) {  printf("%d ", s1[i]); } printf("\n");} void pb(){ int i, k; for(i = 0; i <= n; i ++) {  for(k = 0; k  <= m; k ++)  {   printf("%d ", b[i][k]);  }  printf("\n"); } printf("\n");}  int main(){ //freopen("in.txt", "r", stdin); scanf("%d", &t); int i; for(i = 0; i < t; i ++) {  read();  init();    dp();  //pb();  printf("%d\n", ans); } return 0;}      

评论