POJ - 2096 Collecting Bugs【期望DP】-蒲公英云

POJ - 2096 Collecting Bugs【期望DP】

题意：某个系统中有n个子系统和m个bug类型，该系统每天会出现一个bug （属于某个子系统和某个bug类型），bug的类型是等概率的，bug也是等概率地出现在每个子系统的。问所有子系统都出现bug且所有的bug类型都出现的期望天数。

思路：f[i][j] 表示找到i种bug，找到j个子系统的bug，要求期望天数，所以我们从后往前推。

f[i][j] 发现一个bug属于已知的种类和系统概率为 p1 = (i / n) * (j / s)

f[i + 1][j] 发现一个bug未知的种类但属于已知的系统 p2 = ((n - i) / n ) * (j / s)

f[i][j + 1] 发现一个bug未知系统但属于已知的种类 p3 = (i / n) * ((s - j) / s )

f[i + 1][j + 1] 发现一个bug属于未知系统未知种类， p4 = ( (n - i) / n ) * ( (s - j) / s )

那么f[i][j] = p1 * f[i][j] + p2 * f[i + 1][j] + p3 * f[i][j + 1] + p4 *f[i + 1][j + 1] + 1, 加一是因为发现一个bug需要一天的时间

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define mid ((l + r) >> 1)
const int maxn = 1e3 + 10;
const ll inf = 0x3f3f3f3f;
double f[maxn][maxn];
int main()
{
    int n, s;
    scanf("%d%d", &n, &s);
    f[0][0] = 0;
    for(int i = 0; i <= n; ++i)
    {
        for(int j = 0; j <= s; ++j)
        {
            if(i == 0 && j == 0) continue;
            double p1 = i * j * 1.0 / n / s;
            double p2 = (n - i) * j * 1.0 / n / s;
            double p3 = i * (s - j) * 1.0 / n / s;
            double p4 = (n - i) * (s - j) * 1.0 / n / s;
            f[i][j] = (1 + p2 * f[i + 1][j] + p3 * f[i][j + 1] + p4 * f[i + 1][j + 1]) / (1 - p1);
        }
    }
    printf("%.4f\n", f[0][0]);
    return 0;
}