牛客网 ACM 比赛 62880 K 题：无限重生的 Boss 策略详解

有一个可以无限重生的 Boss，开始时 Boss 有 1 点生命值，当 Boss 被击败后（血量小于等于 0 时），玩家可以获得 1 点积分，此后 Boss 会复活并且血量翻倍 (第一次复活是 2，第二次是 4，第三次是 8，依次类推，复活之后 Boss 满血)，再次击败 Boss 后可以再次获得 1 点积分。 Boss 不会行动，初始时玩家攻击力为 1，玩家可以行动 n 个回合，对于每一个回合玩家可以选择下面三种操作的一个。操作 1：攻击对 Boss 攻击，Boss 降低的血量等于玩家的当前攻击力操作 2：攻击强化攻击力永久 × 2 操作 3：蓄力下次攻击时，攻击力 × 8，可以叠加（两次蓄力后可以 × 64, 但是攻击之后增益消失），只对第一次攻击有收益示例：执行 5 次操作，分别为 22311，那么第一次的攻击时攻击力是 32，第二次的攻击时攻击力是 4

题目要求我们在有限的回合内，选择合适的操作来最大化获得积分的数量。

首先，我们可以观察到，每次击败 Boss 并获得积分后，Boss 的血量都会翻倍。这意味着，我们可以通过不断地击败 Boss 来获得更多的积分。因此，我们的策略应该是尽可能多地击败 Boss。

其次，我们可以注意到，蓄力操作只对第一次攻击有收益。因此，我们应该在蓄力之前尽可能多地进行攻击操作，以增加我们的攻击力。

基于以上观察，我们可以制定以下策略：

首先，我们将尽可能多地进行攻击操作，直到我们的攻击力达到 8。
接下来，我们进行蓄力操作，将攻击力增加到最大值。
之后，我们尽可能多地进行攻击操作，直到我们的回合用完或者 Boss 的血量降低到 0 以下。
如果我们的回合还没有用完，并且 Boss 的血量降低到 0 以下，我们将继续重复步骤 1-3，直到我们的回合用完。

根据以上策略，我们可以用代码来模拟游戏过程，并计算出最终获得的积分数量。

def get_max_score(n, actions):
    score = 0   # 初始积分为 0
    boss_hp = 1 # 初始 Boss 血量为 1
    attack = 1  # 初始攻击力为 1
    charge = 0  # 蓄力次数
    for action in actions:
        if action == 1:  # 攻击操作
            boss_hp -= attack  # 减少 Boss 血量
            if boss_hp <= 0:   # 如果 Boss 被击败
                score += 1     # 获得 1 点积分
                boss_hp = 2**charge  # Boss 复活，血量翻倍
        elif action == 2:  # 攻击强化操作
            attack *= 2     # 攻击力翻倍
        elif action == 3:  # 蓄力操作
            charge += 1     # 蓄力次数加 1
            attack = 8      # 攻击力设为 8
    return score

n = int(input())       # 输入回合数
actions = list(map(int, input().split()))  # 输入操作序列
max_score = get_max_score(n, actions)       # 计算最大积分数量
print(max_score)

以上代码中，我们使用一个循环来遍历操作序列，并根据不同的操作进行相应的处理。在每个操作结束后，我们检查 Boss 的血量是否降低到 0 以下，如果是，则增加积分并重置 Boss 的血量为 2 的蓄力次数次方。最后，我们返回最终的积分数量。

该算法的时间复杂度为 O(n)，其中 n 为回合数。