《Monster Killing》题目分析

本题的背景参考了一款叫作《不思议迷宫》的手游，一道搜索 / 状态压缩DP题目。

数据范围很小，提示我们可能可以搜索完整个状态空间。所以我们第一步是准确估计一下状态总数。

注意题目描述中关于每次行动的说明，告诉我们实际上只能存在一只被翻出且存活的怪物，并且如果有存活的怪物，我们只能击杀它之后才能翻下一个石板。

所以我们可以把一个状态(或者说局面)表示为当前哪些石板已经被翻开以及当前剩余buff层数，同时我们将当前状态剩余HP作为状态的分值，HP越高分值越高。

有同学可能会问，假设我们翻出一个怪物到达一个新的局面，那么这个局面的分值是杀怪前的HP还是杀怪后的HP呢？

答案是杀怪后的HP，同时新状态中的buff层数也应该是杀怪后的层数。因为一旦翻出一只怪物，我们一定要击杀它(或者被杀死)才能翻新的石板。所以我们把杀怪的过程压缩掉了，直接记录杀怪之后的状态。

这样状态总数大约是2^20 * 6 约等于 6 * 10^6。

这样我们就可以通过暴搜+最优化剪枝解决这题。

当然我们也可以通过状态压缩DP求出每个状态的最优值（最高HP）。