Poj 2096 Collecting Bugs (dp求期望)

我会带着你远行 2021-11-04 10:22 224阅读 0赞

[简说期望类问题的解法 - Kicd的日志 - 网易博客][- Kicd_ -]

下面内容参考了：http://blog.csdn.net/morgan\_xww/article/details/6774708

题意：一个软件有s个子系统，会产生n种bug。 某人一天发现一个bug，这个bug属于某种bug，发生在某个子系统中。 求找到所有的n种bug，且每个子系统都找到bug，这样所要的天数的期望。

需要注意的是：bug的数量是无穷大的，所以发现一个bug，出现在某个子系统的概率是1/s， 属于某种类型的概率是1/n。

思路：

dp\[i\]\[j\]表示已经找到i种bug，并存在于j个子系统中，要达到目标状态的天数的期望。

显然，dp\[n\]\[s\]=0，因为已经达到目标了。而dp\[0\]\[0\]就是我们要求的答案。

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和新的一个子系统

以上四种的概率分别为：

> p1 = i\*j / (n\*s)
> 
> p2 = (n-i)\*j / (n\*s)
> 
> p3 = i\*(s-j) / (n\*s)
> 
> p4 = (n-i)\*(s-j) / (n\*s)

又有：期望可以分解成多个子期望的加权和，权为子期望发生的概率，即 E(aA+bB+...) = aE(A) + bE(B) +... 所以：

dp\[i,j\] = p1\*dp\[i,j\] + p2\*dp\[i+1,j\] + p3\*dp\[i,j+1\] + p4\*dp\[i+1,j+1\] + 1; （又过了一天，所以+1）

整理得：

dp\[i,j\] = ( 1 + p2\*dp\[i+1,j\] + p3\*dp\[i,j+1\] + p4\*dp\[i+1,j+1\] )/( 1-p1 )

= ( n\*s + (n-i)\*j\*dp\[i+1,j\] + i\*(s-j)\*dp\[i,j+1\] + (n-i)\*(s-j)\*dp\[i+1,j+1\] )/( n\*s - i\*j )

#include <cstdio>  
    #include <iostream>  
    using namespace std;
    
    double dp[1005][1005];
    
    int main ()
    {
    	int n,s,ns;
    	scanf("%d%d",&n,&s);
    	ns=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;
    			dp[i][j] = ( ns + (n-i)*j*dp[i+1][j] + i*(s-j)*dp[i][j+1] + (n-i)*(s-j)*dp[i+1][j+1] )/( ns - i*j );
    		}
    	printf("%.4lf\n", dp[0][0]);
    	return 0;
    }

[- Kicd_ -]: http://kicd.blog.163.com/blog/static/126961911200910168335852/