HDU 1243 反恐训练营

发表于 | 分类于 | 阅读次数:

（其实还是用LCS的方法就可以了，考虑了好久，起初在数据输入地方就搞错了 T_T）

Max_Score[i][j]: 当第i颗子弹对付第j个恐怖分子的最大得分

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX(x,y) (x)>(y)?(x):(y)
int MaxScore[2005][2005];
char Kind[150],TE[2005],Kill[2005];
int Score[150];
int main()
{
    //freopen("Sample Input.txt","r",stdin);
    int i,N,j;
    int tmp;
    int TLen,KLen;
    while (scanf("%d",&N)!=EOF)
    {
        getchar();
        for ( i = 0; i < N; i++)
            scanf("%c",&Kind[i]);
        getchar();
        for ( i = 0; i < N; i++)
        {
            scanf("%d",&tmp);
            Score[Kind[i]] = tmp;
        }
        getchar();
        scanf("%s%s",Kill,TE);
        KLen = strlen(Kill); TLen = strlen(TE);
        for ( i = 0; i <= KLen; i++)
            MaxScore[i][0] = 0;
        for ( j = 0; j <= TLen; j++)
            MaxScore[0][j] = 0;
        for ( i = 1; i <= KLen; i++)
        {
            for ( j = 1; j <= TLen; j++)
            {
                if ( Kill[i-1]==TE[j-1] )
                    MaxScore[i][j] = MaxScore[i-1][j-1] + Score[TE[j-1]];
                else
                    MaxScore[i][j] = MAX(MaxScore[i-1][j],MaxScore[i][j-1]);
            }
        }
        printf("%d\n",MaxScore[KLen][TLen]);
    }
    return 0;
}