POJ 2096 Collecting Bugs 概率dp 求期望 入门

题意：

一个人很喜欢去发现bug，每一天他能够发现一个bug。现在有个公司聘用他，希望他能从该公司的新软件中找bug。

这个软件由多个子系统构成，要求：

1.每个子系统至少要找到1个bug。

2.每个bug种类至少要找到一个bug。

问，他完成任务所需要的天数期望。

思路：

dp[i][j]：已经在i个子系统中找到bug，并且bug的种类有j种，距离dp[n][m]目标状态还需要的天数的期望。

每天他找到一个bug，有4种可能。

①i+1，j；所发现的bug在新子系统中，此前已经已经发现相同的种类的bug；

②i+1，j+1；所发现的bug在新子系统中，此前还未发现过此类bug；

③i，j；所发现的bug在旧子系统中，此前已经已经发现相同的种类的bug；

④i，j+1；所发现的bug在旧子系统中，此前还未发现过此类bug；

转移方程：

dp[i][j] = dp[i+1][j] * p1 + dp[i+1][j+1] * p2 + dp[i][j] * p3 + dp[i][j+1] * p4;（把dp[i][j]移动到一边）

p1、p2、p3、p4分别对应情况的概率。（系统、bug类型都是随机选择）

code：

#include <cstring>
#include <cstdlib>
#include <cstdio>
#include <iostream>
#include <iomanip>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long LL;

const int MAXN = 1e3+5;

double dp[MAXN][MAXN];

int main()
{
    ios::sync_with_stdio(false);
    int n, s;
    while(cin>>n>>s)
    {
        memset(dp, 0, sizeof(dp));
        for(int i = n; i >= 0; i--)
            for(int j = s; j >= 0; j--)
            {
                if(i == n && j == s) continue;
                double p1 = (n-i)*(s-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 = i*j*1.0/(n*s);
                dp[i][j] = (dp[i+1][j+1]*p1 + dp[i+1][j]*p2 + dp[i][j+1]*p3 + 1.0) / (1.0-p4);
            }

        cout<<fixed<<setprecision(4)<<dp[0][0]<<endl;
    }
    return 0;
}