codeforces 518 D. Ilya and Escalator

http://codeforces.com/problemset/problem/518/D

题意:有n个人排队上一个电梯。。。在某一秒内,队首的人有p的概率上电梯,1-p的概率不动。每个人只有在队首的位置才可以上电梯(也就是每一秒内,最多只有一个人可以上电梯)。电梯无线长(也就是上了电梯就不会离开了),问在第t秒的时候,电梯上的人的个数的数学期望是多少。

思路:一开始推公式的我还是图样。这题是dp.其实也不难想。dp[i][j]表示第i秒时电梯上有j个人的概率。 当j==n的时候,也就是所以人都上了电梯以后。dp[i+1][j]+=dp[i][j],对于其他时刻 dp[i+1][j+1]+=dp[i][j]*p,dp[i+1][j]+=dp[i][j]*(1-p).  初始化dp[0][0]=1,即0时刻电梯上有0个人的概率为1.

 

 

作者: CrazyKK

ex-ACMer@hust,stackoverflow-engineer@sensetime

说点什么

您将是第一位评论人!

提醒
wpDiscuz