自动搬运

查看原文

来自洛谷，原作者为

	MiyazonoKaori 「私の翼は、あなたのために生まれたから」||主页：https://www.luogu.me/paste/vnxgw02d（能看）

搬运于2025-08-24 23:07:02，当前版本为作者最后更新于2025-03-06 19:36:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

让我们回到正题，我使用的是动态规划实现，时间复杂度为 $O(3^q\times 2^n\times n\times k)$，这个时间复杂度看似很高，实际一点也不少，但是我们可以通过剪枝实现。

表示

• s：表示当前的状态，使用状态压缩来表示已经访问过的城市和道具的使用情况。
• f[s]：状态 s 下使用的最少武器数量。
• g[s]：状态 s 下最后一把武器的剩余耐久。

转移

然后就开始推动态转移方程式，我们需要分两种情况：

1. 使用这个道具；
2. 不使用这个道具。

状态转移的核心思想是：从当前状态 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)$$

总结

1. 不使用道具：

   $$f[s \cup \{i\}] = \begin{cases} f[s] & g[s] + a[i] \leq b[f[s]] \\ f[s] + 1 & \text{其它} \end{cases}$$$$g[s \cup \{i\}] = \begin{cases} g[s] + a[i] & g[s] + a[i] \leq b[f[s]] \\ a[i] & \text{其它} \end{cases} $$

2. 使用道具：

   $$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。