问题理解

我们有 $n$ 只怪物，初始生命值为 $h_1, h_2, \dots, h_n$，目标是将所有生命值降到 $1$。

每轮攻击：

• 剑以概率 $p$ 闪耀，以概率 $1-p$ 不闪耀。
• 闪耀时：如果选择攻击，所有怪物生命值 $-1$。
• 不闪耀时：如果选择攻击，选择一只怪物生命值 $-1$。
• 可以在知道闪耀与否后决定是否攻击。

水母采用最优策略，求达成目标的概率。

---

核心观察

设当前怪物中最小生命值为 $l$，那么：

• 最多只能进行 $l-1$ 次全体攻击（因为全体攻击会降低所有怪物的生命值，包括那个生命值最小的怪物，一旦降到 $0$ 以下就不符合规则）。
• 对于生命值为 $h_i$ 的怪物，它至少需要 $h_i - l$ 次单体攻击（因为全体攻击会对它造成 $l-1$ 次伤害，剩下的部分必须由单体攻击完成）。

因此，问题可以归结为：

• 记 $l = \min h_i$（减去目标 $1$ 后）
• 总需要的单体攻击次数为：$$s = \sum_{i=1}^n (h_i - l)$$

---

策略分析

最优策略：

• 在前 $s$ 次剑不闪耀的回合中，每次不闪耀时都选择攻击（因为单体攻击是必需的）。
• 如果 $s > m$，则不可能达成目标，概率为 $0$。

在 $s$ 次不闪耀攻击之后，所有怪物的生命值将相等（都等于 $l$）。

• 此时，每次闪耀的回合如果攻击，所有怪物的生命值会同步减少。
• 每次不闪耀的回合，可以选择攻击当前生命值最高的怪物，使它们尽可能保持均衡。

---

动态规划设计

阶段 1：前 $i$ 轮中恰好有 $j$ 次不闪耀的概率

定义 $g[i][c][x]$：

• $i$：已经进行的轮数
• $c$：当前需要单体攻击的怪物数量（即生命值比最小值大的怪物数）
• $x$：当前最小生命值（减去目标 $1$ 后的值）

初始：$g[0][0][0] = 1$。

转移：

• 如果当前轮剑闪耀（概率 $p$）：
  • 我们必须攻击（因为不攻击会浪费机会，不是最优），所有怪物生命值 $-1$：
    • 如果 $x > 0$：$x$ 减少 $1$，$c$ 不变
    • 如果 $x = 0$：$x$ 恢复为 $l-1$？需要仔细处理
• 如果当前轮剑不闪耀（概率 $1-p$）：
  • 选择攻击一只怪物：
    • 如果 $c > 0$：攻击一只生命值最高的怪物，$c$ 减少 $1$，$x$ 不变
    • 如果 $c = 0$：所有怪物生命值相等，攻击任意一只，$x$ 不变，但需要维护后续平衡

$g$ 转移代码：

g[i][0][x] = g[i-1][0][x-1] * p + max(g[i-1][0][x], g[i-1][n-1][x-1]) * (1-p);
g[i][c][x] = g[i-1][c][x-1] * p + g[i-1][c-1][x] * (1-p);

阶段 2：$s$ 次不闪耀后，剩余的 $k-s$ 轮中达成目标的概率

定义 $f[i][j]$：

• $i$：剩余轮数
• $j$：已经发生的不闪耀次数（$j \le s$）

初始：$f[0][0] = 1$

转移：

$$f[i+1][j] \mathrel{+}= f[i][j] \cdot p$$ $$f[i+1][j+1] \mathrel{+}= f[i][j] \cdot (1-p)$$

即：在 $i$ 轮中恰好发生 $j$ 次不闪耀的概率。

---

合并答案

枚举第 $s$ 次不闪耀发生的时刻：

• 设在第 $i$ 轮结束后，恰好发生了 $s$ 次不闪耀，概率为 $f[i][s]$
• 剩余 $k-i$ 轮中，需要让所有怪物生命值降到 $1$（即 $x$ 从当前值降到 $0$）

在剩余轮次中：

• 初始所有怪物生命值相等（因为 $s$ 次单体攻击已使它们平衡）
• 设当前生命值为 $l - x$（$x$ 是已降低的次数）
• 需要再降低 $x$ 次全体攻击（闪耀时）或单体攻击（不闪耀时）

最优策略：每次不闪耀时攻击当前生命值最大的怪物。 这等价于：在剩余 $k-i$ 轮中，找到最大的 $r$ 使得可以通过 $k-i$ 轮将所有怪物生命值降到 $1$。

计算的代码：

for(int x = 0; x <= min(i - s, m); x++) 
    r = max(r, g[k - i][0][m - x]);

这里 $g[k-i][0][m-x]$ 表示在 $k-i$ 轮中，从生命值 $m-x$（所有怪物相等）降到 $0$ 的概率。

最终答案：

$$\text{ans} = \sum_{i=s}^{k} \left( \max_{x} g[k-i][0][m-x] \right) \cdot f[i][s] $$

---

边界情况

• 如果 $s > k$，输出 $0$（不可能完成足够多的单体攻击）
• 如果初始就有怪物生命值为 $1$（$h_i=1$，则 $h_i-1=0$），需要特殊处理

---

时间复杂度

• $O(n \cdot m \cdot \max h) \approx O(n \cdot m \cdot 400)$
• 对于 $n \le 20$，$m \le 4000$，$t \le 100$，$n$ 总和 $\le 100$，可接受

---

示例验证

样例 1

$n=2, m=2, p=0.1, h=[2,2]$

• 减去目标 $1$ 后：$h=[1,1]$，$l=1$，$s=0$
• 不需要单体攻击，直接计算剩余 $2$ 轮中达成目标的概率
• 结果：$0.91$

样例 2

$n=5, m=5, p=0.2, h=[2,2,2,2,2]$

• $h=[1,1,1,1,1]$，$l=1$，$s=0$
• 只需要全体攻击，失败概率 = 从未闪耀 = $(0.8)^5$
• 成功概率 = $1 - 0.8^5 = 0.67232$

---

总结

本题的关键在于：

1. 将问题分解为必需的 $s$ 次单体攻击和后续的平衡攻击
2. 利用最优策略简化状态：总是攻击生命值最高的怪物
3. 通过动态规划分别计算两阶段的概率分布
4. 合并得到最终答案