3.3 击杀 Boss

发表于 | 更新于 | 分类于 | 阅读次数：

实验任务

小八同学是个游戏高手，面对任何游戏总是游刃有余。但他并不满足于此，他想要知道他和真正的高手之间还有多少的差距，这使得小八开始研究起游戏的运行机制。已知在某个游戏里，英雄和 boss 的初始生命值都是 100，每回合英雄先攻击 boss，然后boss 再攻击英雄。boss 每次打英雄的伤害值固定，英雄打 boss 可以使用普通攻击，也可以使用技能攻击。使用普通攻击每次造成的伤害为 1，不花费任何的魔法值。使用技能时，则每次可以从\(n\)种技能中挑选一种，造成\(b_i\)点伤害，花费魔法值\(a_i\)，剩余魔法值小于\(a_i\)，则无法使用该技能。

英雄的初始魔法值为 100，每秒回复魔法值为 t，但是恢复也不会使魔法值超过 100。（回复魔法值会在英雄发动攻击前进行）

现在小八想通过这些数据了解到打死 boss 最快需要多少时间，又或者英雄会被 boss 杀死。（每秒钟 boss 和英雄都只能进行一次攻击，当生命值小于等于 0，即认为被杀死）

数据输入

第 1 行为三个用一个空格隔开的正整数\(n\ t\ q\)，其中\(n\ (0\leq n\leq 100)\)，表示英雄拥有的技能数，\(t\ (1\leq t\leq 5)\)，为每秒回复的魔法值，\(q\ (q>0)\)，为每次 boss 对英雄的伤害值。

从第 2 行到第\(n+1\)行，第\(j\)行给出了编号为\(j-1\)的技能的基本数据，每行有 2 个非负整数\(a_i\ b_i\)，其中\(a_i\)表示使用该技能花费的魔法值，\(b_i\)表示使用该技能造成的伤害。

数据输出

输出只有一行，表示英雄杀死 boss 的时间，如果英雄被杀死，则输出“Game over”。

输入示例 输出示例
4 2 25
10 5
20 10
30 28
76 70		 4
4 2 25
10 5
20 10
30 28
77 70		 Game over

提示

在两个示例中，除了最后一行数据，其余数据都一样。

其中 boss 打英雄每秒伤害为 25，4 秒之后英雄就会被 boss 打死。也就是说英雄最多有发动四次攻击的机会。

在 4 次攻击里，每一秒的顺序都是英雄先回复魔法值，然后英雄攻击 boss，最后 boss 攻击英雄。由于第一秒的回复值加上 100 会超出上限，所以这两点魔法值无法加入到魔法值总数中。这才导致两个示例的结果不同。

源代码

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
46
#include <stdio.h>
#include <string.h>
#define maxn 105
#define maxp 100
int hurtSum[maxn][maxn];//turn*magic
int ai[maxn]; // 花费
int bi[maxn];  // 伤害
int bosslife = maxp;
int maxHurt = 0;
int n, t, q; //技能数, 魔力恢复值,boss伤害值
int killflag = -1;

int magicUpdate(int magic){
    magic = t + magic;
    return (magic>maxp) ? maxp : magic;
}

int fight(int lifeturn, int magicSum){
    if (lifeturn == 0) return 0;
    if (hurtSum[lifeturn][magicSum]>0) return hurtSum[lifeturn][magicSum];
    int MaxHurt = 0;
    int updateMagic = magicUpdate(magicSum);
    for (int i = 0; i <= n; i++){
        if (updateMagic >= ai[i]){
            int temp = fight(lifeturn - 1, updateMagic - ai[i]) + bi[i];
            if (temp>MaxHurt) MaxHurt = temp;
        }
    }
    if (MaxHurt >= bosslife && (killflag<0 || killflag>lifeturn)) killflag = lifeturn;
    hurtSum[lifeturn][magicSum] = MaxHurt;
    return MaxHurt;
}

int main(){
    memset(hurtSum, 0, sizeof(hurtSum));
    scanf("%d%d%d", &n, &t, &q);
    //普通攻击
    ai[0] = 0, bi[0] = 1;
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &ai[i], &bi[i]);
    //轮数, 魔力值
    fight(maxp / q + (maxp % q != 0), maxp);
    if (killflag>0) printf("%d\n", killflag);
    else printf("Game over\n");
    return 0;
}

设计思路与复杂度分析

由于 boss 的攻击手段确定，那么英雄的最多攻击次数即可确定。则问题简化为英雄能否在给定攻击次数中击毙 boss 。由此得到状态转移方程：\[dp(m,p)=max(b_i+dp(m-1,p + t-a_i)),\ i=0,1,\cdots, n\]其中\(m\)为可攻击次数，\(p\)为魔法值。考虑到状态转移方程不是单向依赖的，无法使用递推形式的\(dp\)，只能使用备忘录方法了。

0%