POJ 2096 Collecting Bugs

题意

给软件挑bug,每天挑出来一个,每个bug都有两个属性:分类和子系统,这两个属性都是完全随机的,已知一共有n个分类,s个子系统,问你挑出的bug完全覆盖全部分类和子系统需要多长时间(求期望)。

思路

优惠券问题的变种,相当于升高到了二维,因此dp数组也要开成二维。

我们设定dp[i][j]表示距离完成任务还有i个分类j个子系统没有覆盖,状态的转移用如下几种:
1.挑出的bug属于全新的分类和子系统
2.挑出的bug仅仅属于全新的分类
3.挑出的bug仅仅属于全新的子系统
4.挑出的bug没有任何新意
这样,我们可以得出状态转移方程:dp[i][j]=\frac{i}{n}\frac{j}{s}dp[i-1][j-1]+\frac{n-i}{n}\frac{j}{s}dp[i][j-1]+\frac{i}{n}\frac{n-j}{s}dp[i-1][j]+\frac{n-i}{n}\frac{n-j}{s}dp[i][j]+1

经过化简可以发现这是个很直接的递推方程了,所以可以很轻松的出答案了。

代码

 

Leave a Reply

Scroll to top