两个字符串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;
}
  

评论