【HDOJ】1243 反恐训练营

LCS.
 1 /* 1243 */
 2 #include <cstdio>
 3 #include <cstring>
 4 #include <cstdlib>
 5 
 6 #define MAXN 2025
 7 #define MAXM 256
 8 
 9 char type[MAXM];
10 int point[MAXM];
11 
12 char bullet[MAXN];
13 char kbfz[MAXN];
14 int dp[MAXN][MAXN];
15 int  n;
16 
17 int min(int a, int b) {
18     return a<b ? a:b;
19 }
20 
21 int max(int a, int b) {
22     return a>b ? a:b;
23 }
24 
25 int abs(int x) {
26     return x<0 ? -x:x;
27 }
28 
29 int main() {
30     int i, j, k;
31     int l1, l2;
32     
33     #ifndef ONLINE_JUDGE
34         freopen("data.in", "r", stdin);
35     #endif
36     
37     while (scanf("%d", &n) != EOF) {
38         memset(point, 0, sizeof(point));
39         scanf("%s", type);
40         for (i=0; i<n; ++i) {
41             scanf("%d", &k);
42             point[type[i]] = k;
43         }
44         scanf("%s", bullet+1);
45         scanf("%s", kbfz+1);
46         l1 = strlen(bullet+1);
47         l2 = strlen(kbfz+1);
48         for (i=0; i<=max(l1, l2); ++i) {
49             dp[0][i] = 0;
50             dp[i][0] = 0;
51         }
52         for (i=1; i<=l1; ++i) {
53             for (j=1; j<=l2; ++j) {
54                 if (bullet[i] == kbfz[j]) {
55                     dp[i][j] = dp[i-1][j-1] + point[bullet[i]];
56                 } else  {
57                     k = max(dp[i-1][j], dp[i][j-1]);
58                     dp[i][j] = max(k, dp[i-1][j-1]);
59                 }
60             }
61         }
62         printf("%d
", dp[l1][l2]);
63     }
64     
65     return 0;
66 }