poj - 2096 概率dp (找bug)

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：一个人一天只能找1个bug ,这个bug属于s个子系统中的某一个子系统，属于n种bug 中的某一种 ,求 这个人找出n种bug ,并且s个系统都bug的期望 （每个系统的一定可以找出bug）

一直在纠结 dp[i][j]是不是自己的子期望 ，先这么想吧：dp[i][j] 的子期望是四种状态 ，所以在这里面 ，dp[i][j]状态转移方程可以这么写 ，但是要从它表示的意义去理解

撸代码：

#include<stdio.h>
double dp[1011][1011];
/*
明确 期望的求法 ：（可能结果的概率乘以其结果）的总和；期望可以分成多个子期望的加权和dp[i][j] 表示 已找到的i种 属于j个系统之中的bug，达到目标天数的期望
dp[n][s] 就是目标本身 ，所以为0
dp[i][j] 转化为：
dp[i][j] 发现1个bug 属于 i种bug和j个子系统中 p1= (i*j)/(n*s)
dp[i+1][j] 发现1个bug 不属于i种bug ,但属于已找到的j个子系统中 p2 = (i+1)*j/(n*s)
dp[i][j+1] 发现1个bug 属于i种bug，但不属于已找到的j个子系统中p3 = i*(j+1)/(n*s)
dp[i+1][j+1] 发现1个bug ，不属于 i种bug,也不属于j个子系统中 p4 = (i+1)*(j+1)/(n*s)
期望可以分解成多个期望的加权和
四种状态是子期望，因为每个bug找1天，所以加1
dp[i][j] = dp[i][j]*p1+dp [i+1][j]*p2+dp[i][j+1]*p3+dp[i+1][j+1]*p4+1;
移项：状态转移方程
*/
int main()
{
int s,n;
while(~scanf("%d%d",&n,&s))
{
dp[n][s]=0;
for(int i=n;i>=0;i--)
{
for(int j=s;j>=0;j--)
{
if(i==n&&j==s) continue;
double p2=dp[i+1][j]*(n-i)*j;
double p3=dp[i][j+1]*i*(s-j);
double p4=dp[i+1][j+1]*(n-i)*(s-j);
dp[i][j]=(n*s+p2+p3+p4)/(n*s-i*j);
}
}
printf("%.4f\n",dp[0][0]);
}
return 0;
}