[poj2096]Collecting Bugs(概率dp)

题意：一个软件有s个子系统，会产生n种bug，某人一天发现一个bug,这个bug属于一个子系统，属于一个分类，每个bug属于某个子系统的概率是1/s,属于某种分类的概率是1/n，问发现n种bug,每个子系统都发现bug的天数的期望。

解题关键：dp求期望入门题，一直说概率正推，期望逆推，为什么呢？今天终于搞明白了，一个状态转化到n个状态的概率分别为......，说明该状态可以由他转化到的n个状态转化而来，从而推公式得到该状态的期望转移方程。

令$dp[i][j]$表示已经发现$i$种bug，包含于$j$个子系统，则:

$dp[i][j]$状态可以转化成以下四种：
$dp[i][j]$发现一个bug属于已经找到的$i$种bug和$j$个子系统中
$dp[i+1][j]$ 发现一个bug属于新的一种bug，但属于已经找到的$j$种子系统
$dp[i][j+1]$发现一个bug属于已经找到的$i$种bug，但属于新的子系统
$dp[i+1][j+1]$发现一个bug属于新的一种bug和新的一个子系统

四个概率分别为：

[egin{array}{l}
{p_1} = i*j/(n*s)\
{p_2} = (n - i)*j/(n*s)\
{p_3}{ m{ }} = { m{ }}i*(s - j)/(n*s)\
{p_4}{ m{ }} = { m{ }}left( {n - i} ight)*left( {s - j} ight)/left( {n*s} ight)
end{array}]

 转移方程为：$dp[i][j] = {p_1}*dp[i][j] + {p_2}*dp[i + 1][j] + { m{ }}{p_3}*dp[i][j + 1] + { m{ }}{p_4}*dp[i + 1][j + 1] + 1$

移项得到：$dp[i][j] = ({p_2}*dp[i + 1][j] + { m{ }}{p_3}*dp[i][j + 1] + { m{ }}{p_4}*dp[i + 1][j + 1] + 1)/(1 - {p_1})$

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cstdlib>
 4 #include<iostream>
 5 #include<cmath>
 6 #include<algorithm>
 7 using namespace std;
 8 typedef long long ll;
 9 double dp[1002][1002]; 
10 int main(){
11     int n,s;
12     scanf("%d%d",&n,&s); 
13     for(int i=n;i>=0;i--){
14         for(int j=s;j>=0;j--){
15             if(i==n&&j==s) continue;
16             double p1,p2,p3,p4;
17             p1=1.0*i*j/n/s;
18             p2=1.0*(n-i)*j/n/s;
19             p3=1.0*i*(s-j)/n/s;
20             p4=1.0*(n-i)*(s-j)/n/s;
21             dp[i][j]=(1+p2*dp[i+1][j]+p3*dp[i][j+1]+p4*dp[i+1][j+1])/(1-p1);
22         }
23     }
24     printf("%.10f
",dp[0][0]);
25     return 0;
26 }