这是一题典型的最大公共子序列。一开始没看出来，直到写dp写不下去，赶紧去翻busycai大牛的程序才恍然大悟。

    用f[i][k]表示a取到i，b取到k时最大的权值。f[i][k] = max (f[i - 1][k - 1] + v[i], f[i][k - 1], f[i - 1][k])。其中第一个表示i和k时取到相同的字符。

#include <cstdio>
#include <string>

int v[501], n, ans, f[2001][2001], len;
char str[2][2001];

int dp ()
{
 int i, k;
 len = strlen (str[0]);
 memset (f, 0, sizeof(f));

 for (i = 1; i <= len; i ++)
 {
  for (k = 1; k <= len; k ++)
  {
   if (str[0][i - 1] == str[1][k - 1])
   {
    f[i][k] = f[i - 1][k - 1] + v[str[0][i - 1]];
   }
   int mx = f[i - 1][k] > f[i][k - 1] ? f[i - 1][k] : f[i][k - 1];
   if (mx > f[i][k]) f[i][k] = mx;
  }
 }
 return f[len][len];
}
 

int main ()
{
 //freopen ("in.txt", "r", stdin);
 while (scanf ("%d", &n) != EOF)
 {
  int i, value;
  char ch;
  for (i = 0; i < n; i ++)
  {
   getchar ();
   scanf ("%c %d", &ch, &value);
   v[ch] = value;
  }
  scanf ("%s %s", &str[0], &str[1]);  
  printf ("%d\n", dp ());
  //pf ();
 }
 return 0;
}
  

评论