题意
给软件挑bug,每天挑出来一个,每个bug都有两个属性:分类和子系统,这两个属性都是完全随机的,已知一共有n个分类,s个子系统,问你挑出的bug完全覆盖全部分类和子系统需要多长时间(求期望)。
思路
优惠券问题的变种,相当于升高到了二维,因此dp数组也要开成二维。
我们设定dp[i][j]表示距离完成任务还有i个分类j个子系统没有覆盖,状态的转移用如下几种:
1.挑出的bug属于全新的分类和子系统
2.挑出的bug仅仅属于全新的分类
3.挑出的bug仅仅属于全新的子系统
4.挑出的bug没有任何新意
这样,我们可以得出状态转移方程:
经过化简可以发现这是个很直接的递推方程了,所以可以很轻松的出答案了。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 |
#include <iostream> #include <algorithm> #include <queue> #include <vector> #include <cstdlib> #include <cstdio> #include <string> #include <cstring> #include <ctime> #include <iomanip> #include <cmath> #include <set> #include <stack> #include <cmath> using namespace std; double dp[1010][1010]; int main(){ int in = 0,im = 0; while (cin >> in >> im) { double n = in,m = im; memset(dp, 0, sizeof(dp)); dp[0][0] = 0; for (int ii = 1; ii <= in; ii++) { double i = ii; dp[ii][0] = dp[ii-1][0] + n/i; } for (int ii = 1; ii <= im; ii++) { double i = ii; dp[0][ii] = dp[0][ii-1] + m/i; } for (int ii = 1; ii <= in; ii++) { for (int ij = 1; ij <= im; ij++) { double i = ii,j = ij; dp[ii][ij] = (i*j)*dp[ii-1][ij-1]+(n-i)*j*dp[ii][ij-1]+i*(m-j)*dp[ii-1][ij]+m*n; dp[ii][ij] /= m*n-(n-i)*(m-j); } } printf("%.4lf\n",dp[in][im]); } return 0; } |