题解 | #Monster Killer# #概率期望#

牛客43084A - Monster Killer

• https://ac.nowcoder.com/acm/contest/43084/A
• 难度：绿～蓝

题意

有 $n(n\le 10^3)n(n\backslash leq\; 10^3)$ 个怪物，每种怪物的抵御力为 $a_{i}a\_i$

初始时，主人公的战斗力为 $00$，主人公需要按顺序击败这些怪物

在某次战斗中，假设主人公的战斗力为 $mm$，那么有如下情况：

• $m=a_{i}m=a\_i$，他击败了当前怪物
• $m>a_{i}m>a\_i$，他击败了当前怪物，并且有 $p_{i}p\_i$ 的概率他的战斗力变为 $m-1m-1$
• ，他无法击败当前怪物，并且有 $p_{i}p\_i$ 的概率他的战斗力变为 $m+1m+1$

给出$a_{i}a\_i$，$p_{i}p\_i$，问：要把所有怪物都击败，所需要的战斗次数的期望

思路1（倒推）

$dp[i][j]dp[i][j]$ 代表第 $ii$ 轮战斗，主人公有 $jj$ 的战斗力。从当前情况开始，一直到击败所有怪物的期望。

思路2（正推）

• $f[i][j]f[i][j]$ 代表：第 $ii$ 轮战斗，主人公有 $jj$ 的战斗力。出现这种状态的概率
• $g[i][j]g[i][j]$ 代表：第 $ii$ 轮战斗，主人公有 $jj$ 的战斗力。从起点到该状态的操作次数的期望

转移注意事项

转移时，先转移 $ff$，等待 $ff$ 完全转移结束后，再转移 $gg$

具体实现： 设 $s_1,s_2,s_{3}s\_1,s\_2,s\_3$ 为之前的状态，$p_1,p_2,p_{3}p\_1,p\_2,p\_3$ 为之前的状态对应的概率，$e_1,e_2,e_{3}e\_1,e\_2,e\_3$ 为之前的状态对应的期望，$q_1,q_2,q_{3}q\_1,q\_2,q\_3$ 为之前的状态能转移到当前状态的概率。 $ss$ 为当前状态，$pp$ 为当前的状态对应的概率，$ee$ 为当前的状态对应的期望。