牛客练习赛114E Kevin的抽奖黑幕

题目链接

E的官解用的是期望dp的标准做法，其实赛时通过的大部分选手用的是概率dp拆开算期望。很多地方会看到这样的说法：通常情况下，期望dp从后往前递推，概率dp从前往后递推。这里的“前”和“后”其实指的并不是正序循环和逆序循环，而是起始状态和终止状态。在本题中，起始状态为未开始抽奖，终止状态为轮抽奖过后。那么期望dp是从轮抽奖之后的状态递推到未开始抽奖的状态，概率dp是从未开始抽奖的状态递推到轮抽奖结束的状态。记抽中概率为win = k / n , 未抽中概率lose = 1 - k / n。

概率dp

思路

这里的概率dp用到了期望的定义和线性性质，为了方便理解，此处不引入公式，只探讨直观上的理解。如果不考虑“黑幕”，显然轮抽奖过后奖品总数的期望为，那么我们只需要再加上“黑幕”部分的贡献即可。

定义

表示当前第轮结束后，该同学连续轮（包括当前轮）没有抽到奖的概率。注意这里1至轮对应的范围为，的范围为。

转移

初始状态, 表示未开始抽奖时概率为1。其余全为0，从初始状态正序循环计算转移。

1. 第轮结束时抽中奖

此时的结果为，由两部分构成。要么第轮是连续轮未抽中奖，由转移而来; 要么第轮抽中奖，由 转移而来：

2.第轮结束时未中奖

此时的结果为, 由上一轮一直未中奖的状态乘当前轮未中奖的概率转移而来：

计算答案

每次计算转移前，将当前触发“黑幕”（连续轮未获奖）的概率 累加到中。这样累加轮的结果表示每一个人由于“黑幕”而获得奖品的概率总和。由于每次黑幕一个人只获得一个奖品，而这个人又是独立的，由期望的线性性质, 就是“黑幕”对于奖品总数的期望的贡献。

期望dp

思路

官解的思路是标准的期望dp做法。设计状态时考虑从当前状态到终止状态这个过程的期望，然后从终止状态（抽完奖）一步一步转移到起始状态（还没开始抽奖）。

定义

表示某个同学当前第轮开始前，之前已经连续轮没有抽到奖, 从此状态一直到轮抽奖结束时，该同学获得奖品数量的期望（也就是算第轮能获得的奖品数量，注意需要计算当前轮抽中的奖品）。表示该同学获得奖品数量的期望。奖品总数是个人获得的，由抽奖的随机性和期望的线性性，答案即为。需要说明的是，这里1至轮对应的的下标为, 和前面概率dp的下标有所不同。

转移

初始状态全0，逆序循环从终止状态递推到起始状态。当前有两种情况：

1. j == d - 1

此时表示当前第轮开始前已经连续轮未获奖,那么无论这一轮是否抽中奖，这一轮结束后的状态都是中奖，该同学都会获得一个奖品。因此当前同学获得奖品的期望就是当前轮次获得的一个奖品和后面轮次获得的奖品期望：

2.

如果这一轮中奖，那么该同学将会获得一个当前轮次抽中的奖品加上后续f[i+1][0]数量的奖品；如果这一轮不中奖，那么该同学将会获得后续f[i+1][j+1]数量的奖品。按照期望的定义式分配一下概率即可：

两种方法参考代码

上述解法中dp的第一维均可以压缩掉，python解法实现了维度压缩后的版本，时间优化明显。

C++

python

概率dp和期望dp的转移顺序探讨

概率dp要顺推容易理解，因为起始状态的概率为1，之后的状态都能从起始转移得到。而期望dp逆推的原因，参见《算法竞赛进阶指南》作者李煜东老师的说明： 为什么通常期望dp要倒推？