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;
}