自动搬运

查看原文

来自洛谷，原作者为

	__stdcall **

搬运于2025-08-24 21:46:50，当前版本为作者最后更新于2017-04-03 14:17:34，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

一道不简单的概率和期望dp题

根据期望的线性性质，容易想到，可以算出每张卡的期望伤害，然后全部加在一起

手算样例之后发现是正确的，那么我们只要求出每张卡的实际被使用的概率就可以了

记第$i$张卡的实际被使用的概率为$fp[i]$

那么答案就是

$\Large\sum\limits_{i=0}^{n-1}fp[i]\cdot d[i]$

如何求出$fp[i]$？

首先考虑第一张卡的$fp$，也就是$fp[0]$，应该为

$\Large fp[0]=1-(1-p[i])^{r}$

这个很容易理解，因为$(1-p[i])^r$就是这张卡从头到尾始终憋着不出的概率

那么对于后面的$fp$应该怎么求呢

有个条件很烦人，就是在每一轮中，出了一张卡的时候立即结束该轮

那么下面就轮到dp上场啦！

令$f[i][j]$表示在所有的$r$轮中，前$i$张卡中一共出了$j$张的概率，那么就可以用$O(n)$的时间算出$fp[i](i>0)$

枚举前$i-1$轮选了$j$张牌，那么有$j$轮不会考虑到第$i$张牌，也就是有$r-j$轮会考虑到第$i$张牌

那么根据上面的分析，$1-(1-p[i])^{r-j}$就是在$r-j$轮中使用过第$i$张牌的概率，式子：

$\Large fp[i]=\sum\limits_{j=0}^{r}f[i-1][j]\cdot(1-(1-p[i])^{r-j})(i>0) $

接下来只要写出$f[i][j]$的转移方程就好了，分两种情况讨论

第一种，$f[i][j]$从$f[i-1][j]$转移过来，即第$i$张牌最终没有选，始终不选第$i$张牌的概率是$(1-p[i])^{r-j}$

$\Large f[i][j]+=f[i-1][j]\cdot(1-p[i])^{r-j}(i>0)$

第二种，当$j>0$时，$f[i][j]$可以从$f[i-1][j-1]$转移过来，表示最终选择了第$i$张牌

这时候，有$j-1$轮没有考虑到第$i$张牌，所以考虑到第$i$张牌的轮数是$r-j+1$，最终选择的概率为$1-(1-p[i])^{r-j+1}$

$\Large f[i][j]+=f[i-1][j-1]\cdot(1-(1-p[i])^{r-j+1})(i>0,j>0) $

然后就没了，总时间复杂度$O(Tnr)$，具体细节看代码

因为洛谷上有点卡时，所以预处理了$(1-p[i])$的幂

http://www.cnblogs.com/mlystdcall/p/6661858.html