首页 > 代码库 > Codeforces 284E(概率)

Codeforces 284E(概率)

题意:

  在T秒内,按输入顺序给出n首曲子的播放顺序,玩家需要从第一曲向后听。

  第i首曲子有pi和ti两个属性,pi代表在当前这1秒内有pi/100的概率听出这首曲子是什么,

  ti代表如果一直持续听ti秒后,必定会听出曲名,只有在辨识出当前曲子之后才能开始听下一曲。

  当辨识出所有曲目后或时间超过了T秒,游戏结束,在T秒时辨识出的曲子也可以加入答案。

  问游戏结束时辨识出的曲子数目的期望值是多少,要求相对误差或绝对误差不超过1e-6。

  1 <= n <= 5000, 1 <= T <= 5000, 0 <= pi <= 100, 1 <= ti <= T。

分析:

     技术分享

    P(x>=i)的含义就是在T秒内能听出第i首曲子的概率

    f[i][j]表示听出了前i首曲子,一共用了j秒时间的概率

    枚举第i首曲子用了几秒听,那么有

    技术分享

    注意这样是O(nT^2)的,会TLE

    设那个求和式为s(i,j),那么发现s(i,j)可由s(i,j-1)递推得到,所以这样时间就是O(nT)的

    那么P(x>=i)=Σf(i,j) (j<=T)

Codeforces 284E(概率)