POJ - 2096 Collecting Bugs【期望DP】

àì夳堔傛蜴生んèń 2023-06-02 13:54 15阅读 0赞

题意：某个系统中有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;
    }