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