题解 P3239 【[HNOI2015]亚瑟王】

· · 题解

一道不简单的概率和期望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