首页 > 其他 > 详细

poj2096(概率dp)

时间:2018-08-18 00:27:51      阅读:218      评论:0      收藏:0      [点我收藏+]

src:http://poj.org/problem?id=2096

题意: 一个软件有s个子系统,会产生n种bug  某人一天发现一个bug,这个bug属于一个子系统,属于一个分类 每个bug属于某个子系统的概率是1/s,属于某种分类的概率是1/n 问发现n种bug,每个子系统都发现bug的天数的期望。

解答:https://blog.csdn.net/morgan_xww/article/details/6774708   https://www.cnblogs.com/kuangbin/archive/2012/10/02/2710606.html

转自kuangbin博客
dp[i][j]表示已经找到i种bug,j个系统的bug,达到目标状态的天数的期望 dp[n][s]=0;要求的答案是dp[0][0]; dp[i][j]可以转化成以下四种状态: dp[i][j],发现一个bug属于已经有的i个分类和j个系统。概率为(i/n)*(j/s); dp[i][j+1],发现一个bug属于已有的分类,不属于已有的系统.概率为 (i/n)*(1-j/s); dp[i+1][j],发现一个bug属于已有的系统,不属于已有的分类,概率为 (1-i/n)*(j/s); dp[i+1][j+1],发现一个bug不属于已有的系统,不属于已有的分类,概率为 (1-i/n)*(1-j/s);
整理便得到转移方程

这里已知的是[n][s]      一般求概率是正推,求期望是逆推。通过题目可以体会到这点。

ac代码:

 

poj2096(概率dp)

原文:https://www.cnblogs.com/WindFreedom/p/9495885.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!