poj2096 Collecting Bugs (概率DP)

题目描述

一个软件有s个子系统，会产生n种bug。某人一天发现一个bug，这个bug属于一个子系统，属于一个分类。每个bug属于某个子系统的概率是1/s,属于某种分类的概率是1/n 。则每个子系统中找到至少一个bug，并且每个类别至少有一个bug所需天数的期望？

输入

1 2

输出

3.0000

解法

考虑概率期望DP

状态表示：

f[i][j]:当前已经发现了i种bug，且这i种bug属于j个子系统,此状态到结束状态所需的期望天数
∴f[n][s]=0

状态计算：

对于f[i][j]的状态转移，有以下几种情况：
	1.新发现的bug属于已经发现的i个种类，属于已经发现的j个子系统
	2.新发现的bug属于已经发现的i个种类，不属于已经发现的j个子系统
	3.新发现的bug不属于已经发现的i个种类，属于已经发现的j个子系统
	4.新发现的bug不属于已经发现的i个种类，不属于已经发现的j个子系统

1:p1=(i/n) * (j/s)
2:p2=(i/n) * (s-j)/s
3:p3=(n-i)/n * j/s
4:p4=(n-i)/n * (s-j)/s

f[i][j]=p1*(f[i][j]+1)+p2*(f[i][j+1]+1)+p3*(f[i+1][j]+1)+p4*(f[i+1][j+1])

对于等式两边同时含有f[i][j]的情况，我们可以通过移项合并的方法解决

代码：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 1010;
double f[N][N];
int n, s;

double dp(int i, int j) //记忆化搜索
{
    if (f[i][j] >= 0)
        return f[i][j];

    f[i][j] = 0;
    if(i+1<=n&&j<=s)
        f[i][j] += 1.0 * (n - i) * j / (n * s - i * j) * dp(i + 1, j);
    if(i<=n&&j+1<=s)
        f[i][j] += 1.0 * i * (s - j) / (n * s - i * j) * dp(i, j + 1);
    if(i+1<=n&&j+1<=s)
        f[i][j] += 1.0 * (n - i) * (s - j) / (n * s - i * j) * dp(i + 1, j + 1);
    f[i][j] += 1.0 * n * s / (n * s - i * j);
    return f[i][j];
}

int main()
{
    cin >> n >> s;
    memset(f, -1, sizeof f);
    f[n][s] = 0;
    printf("%.5lf", dp(0, 0));
}