hdu 1243 反恐训练营(dp 最大公共子序列变形)

 1 #include <cstring>
 2 #include <cstdlib>
 3 #include <cstdio>
 4 #include <iostream>
 5 #include <algorithm>
 6 using namespace std;
 7 const int maxn = 2000+10;
 8 
 9 char s[maxn], x[maxn], y[maxn];
10 int f[3000], val[maxn], d[maxn][maxn];
11 int main()
12 {
13     int n, i, j;
14     int sum;
15     while(~scanf("%d", &n))
16     {
17         sum = 0;
18         scanf("%s", s);
19         for(i = 0; i < n; i++)
20             scanf("%d", &val[i]);
21         for(i = 0; i < strlen(s); i++)
22             f[s[i]] = val[i];
23         scanf("%s%s", x, y);
24         int len1 = strlen(x);
25         int len2 = strlen(y);
26         for(i = 0; i <= len1; i++)
27             d[i][0] = 0;
28         for(i = 0; i <= len2; i++)
29             d[0][i] = 0;
30         for(i = 1; i <= len1; i++)
31             for(j = 1; j <= len2; j++)
32                 if(x[i-1]==y[j-1])
33                 {
34                     d[i][j] = d[i-1][j-1] + f[x[i-1]];
35                 }
36                 else
37                 {
38                     if(d[i-1][j] > d[i][j-1])
39                         d[i][j] = d[i-1][j];
40                     else
41                         d[i][j] = d[i][j-1];
42                 }
43         printf("%d\n", d[len1][len2]);
44     }
45     return 0;
46 }