【POJ 2096】:Collecting Bugs 概率DP

传送门

题意

一个软件有 $s$ 个子系统，这个软件会产生 $n$ 种 $b u g$ 。
某人一天发现一个 $b u g$ ，这个 $b u g$ 属于 $n$ 种 $b u g$ 中的某种 $b u g$ ，发生在某个子系统中。
求找到所有的 $n$ 种 $b u g$ ，且每个子系统都找到 $b u g$ ，这样所要的天数的期望。

分析

后悔没有好好学概率论了。。。。
设 $f_{i,j}$ 为已经在 $j$ 个子系统中找到 $i$ 种bug，距离题目要求的期望，所以 $f [0] [0] = 0$
然后列出状态转移方程

f[i][j]  = f[i][j] * p1 + f[i 1][j] * p2 + f[i][j + 1] * p3 + f[i + 1][j + 1] * p1;

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>using namespace std;const int N = 1e3 + 10;
double f[N][N];
int n, m;int main() {scanf("%d%d", &n, &m);for (int i = n; ~i; i--)for (int j = m; ~j; j--) {if (i + j == m + n) continue;double p = n * m;double p1 = 1.0 - 1.0 * i * j / p;double p2 = 1.0 * (n - i) * (m - j) / p;double p3 = 1.0 * (n - i) * j / p;double p4 = 1.0 * i * (m - j) / p;f[i][j] = (f[i + 1][j + 1] * p2 + f[i + 1][j] * p3 + f[i][j + 1] * p4 + 1) / p1;}printf("%.4lf\n", f[0][0]);return 0;
}