首页 > 代码库 > 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(概率)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。