题解：P11400 [Code+#8 初赛] 打怪游戏
_MiyazonoKaori_ · · 题解
@yuruilin2026 和@Hootime 两个大佬认为这是道水题，一眼秒了，于是让我这个蒟蒻来做。
然后我直接输出 FALL，成功获得了 29 pts。
不可以，总司令。
让我们回到正题，我使用的是动态规划实现，时间复杂度为
表示
s：表示当前的状态，使用状态压缩来表示已经访问过的城市和道具的使用情况。f[s]：状态s下使用的最少武器数量。g[s]：状态s下最后一把武器的剩余耐久。
转移
然后就开始推动态转移方程式，我们需要分两种情况：
- 使用这个道具；
- 不使用这个道具。
状态转移的核心思想是：从当前状态 s 出发，访问一个新的城市 i，并更新状态 s 和对应的 f[s] 和 g[s]。
1. 状态转移
假设当前状态为 s，尝试访问一个新的城市 i：
-
如果当前武器的剩余耐久
g[s]加上怪物i的血量a[i]不超过当前武器的耐久b[f[s]]，则可以直接使用当前武器击败怪物i，并更新状态s和f[s]、g[s]。转移方程：
f[s \cup \{i\}] = f[s] g[s \cup \{i\}] = g[s] + a[i] -
如果当前武器的剩余耐久
g[s]加上怪物i的血量a[i]超过当前武器的耐久b[f[s]]，则需要丢弃当前武器并尝试使用下一把武器。转移方程：
f[s \cup \{i\}] = f[s] + 1 g[s \cup \{i\}] = a[i]
2. 使用道具的状态转移
如果城市 i 有道具 d[i]，则可以使用道具来减少怪物 i 的血量。假设当前状态为 s，尝试访问一个新的城市 i 并使用道具 d[i]：
-
如果当前武器的剩余耐久
g[s]加上减少后的怪物血量max(a[i] - d[i], 0)不超过当前武器的耐久b[f[s]]，则可以直接使用当前武器击败怪物i，并更新状态s和f[s]、g[s]。转移方程：
f[s \cup \{i\}] = f[s] g[s \cup \{i\}] = g[s] + \max(a[i] - d[i], 0) -
如果当前武器的剩余耐久
g[s]加上减少后的怪物血量max(a[i] - d[i], 0)超过当前武器的耐久b[f[s]]，则需要丢弃当前武器并尝试使用下一把武器。转移方程：
f[s \cup \{i\}] = f[s] + 1 g[s \cup \{i\}] = \max(a[i] - d[i], 0)
总结
-
不使用道具：
f[s] & g[s] + a[i] \leq b[f[s]] \\ f[s] + 1 & \text{其它} \end{cases} g[s] + a[i] & g[s] + a[i] \leq b[f[s]] \\ a[i] & \text{其它} \end{cases} -
使用道具：
f[s \cup \{i\}] = \begin{cases} f[s] & g[s] + \max(a[i] - d[i], 0) \leq b[f[s]] \\ f[s] + 1 & \text{其它} \end{cases} g[s \cup \{i\}] = \begin{cases} g[s] + \max(a[i] - d[i], 0) & g[s] + \max(a[i] - d[i], 0) \leq b[f[s]] \\ \max(a[i] - d[i], 0) & \text{其它} \end{cases}
答案
我们需要找到所有城市都被访问过的状态，即 s = (1 << n) - 1，并检查 f[s] 是否小于 k。如果 f[s] < k，则输出 f[s] + 1 和 b[f[s]] - g[s]；否则输出 FAIL。