poj 2096 Collecting Bugs

题目描述

http://poj.org/problem?id=2096

Solution

我们令 $f[i][j]$ 表示收集了 $i$ 种，属于 $j$ 个系统到收集 $n$ 种，属于 $m$ 个系统的期望天数

能够得到转移 $f[i][j]=\frac{i}{n}\frac{i}{m}f[i][j]+\frac{n-i}{n}\frac{m-j}{m}f[i+1][j+1]+\frac{n-i}{n}\frac{i}{m}f[i+1][j]+\frac{i}{n}\frac{m-j}{m}f[i][j+1]+1$

#include <iostream>
#include <cstdio>
#include <iomanip>
#define maxn 1010
using namespace std;

int n, m;

double f[maxn][maxn];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m; f[n][m] = 0;
    for (int i = n; ~i; --i)
        for (int j = m; ~j; --j) {
            if (i == n && j == m) continue;
            double t1 = f[i + 1][j + 1] * (n - i) / n * (m - j) / m;
            double t2 = f[i + 1][j] * (n - i) / n * j / m;
            double t3 = f[i][j + 1] * i / n * (m - j) / m; 
            double t4 = 1 - 1.0 * i / n * j / m;
            f[i][j] = (t1 + t2 + t3 + 1) / t4;
        }
    cout << fixed << setprecision(4) << f[0][0] << "\n";
    return 0;
}