FTL 题解

思路

两次同时发射之间形成一个独立阶段。若阶段内第一门炮发射 $a$ 次、第二门炮发射 $b$ 次，且最后一次同时发射，则阶段伤害和耗时分别为

阶段结束后两门炮同时重新开始充能，因此不同阶段可以拼接。

做法

子任务 1

递归枚举下一次动作是单独发射第一门炮、单独发射第二门炮或同时发射。状态记录当前时间与两门炮的下一次可用时间，复杂度为 $O(3^h)$。

子任务 2

枚举所有 $a,b\ge1$ 的双炮阶段，再加入两种单炮阶段。以已造成伤害为状态做完全背包式最短时间 DP。阶段数为 $O(h^2)$，总复杂度为 $O(h^3)$。

满分算法

很多不同的 $(a,b)$ 会造成相同或超过 $h$ 的伤害。先用数组 $best[d]$ 记录造成恰好 $d$ 点截断伤害的最短阶段时间。枚举所有 $(a,b)$ 只需 $O(h^2)$，随后只保留每个伤害量的最优阶段。

令 $dp[x]$ 表示完整阶段结束时造成至少 $x$ 点截断伤害的最短时间。枚举所有保留的阶段转移，复杂度也是 $O(h^2)$。

正确性证明

在任意发射序列中，以每次双炮同时发射为界切分。每个含双炮发射的阶段，设两门炮分别共发射 $a,b$ 次。第一门炮完成这些发射至少需要 $at_1$，第二门至少需要 $bt_2$，通过适当延迟较快一门炮的首次或中间发射，可以在 $\max(at_1,bt_2)$ 时同时完成最后一次发射。该阶段前 $a+b-2$ 次单炮射击各扣一次护盾，最后一次双炮只扣一次护盾，所以总伤害为 $a(p_1-s)+b(p_2-s)+s$。最后一次双炮使两门炮同时进入充能，故之后的最优决策与之前无关。

没有双炮发射的尾段可拆成若干单炮阶段。因此任何合法方案都对应若干枚举阶段的拼接；反过来，每个枚举阶段及其任意拼接都可按上述时刻实际执行。$best$ 只删除同伤害下耗时更长的阶段，不会删除最优方案。伤害 DP 枚举所有阶段拼接，所以 $dp[h]$ 恰为最短时间。

复杂度

时间复杂度为 $O(h^2)$，空间复杂度为 $O(h)$。