这是一题典型的最大公共子序列。一开始没看出来，直到写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;}  

评论