程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj 2096 Collecting Bugs(期望)

poj 2096 Collecting Bugs(期望)

編輯：C++入門知識

poj 2096 Collecting Bugs(期望)

程序的bug有n個子集，s個種類。每一個bug屬於每個子集的概率為1/n，每一個bug屬於每個種類的概率為1/s，問每個子集且每個種類都有bug的期望。

求期望，設dp[i][j]表示已有bug屬於i個子集，j個種類的期望，現已知終態為dp[n][s] = 0，dp[i][j]可由逆推而得：

dp[i][j]，新的bug屬於已有的i個子集j個分類，概率為i/n * j/s;

dp[i][j+1]，新的bug屬於已有的i個子集但不屬於已有的j個分類，概率為i/n * (1 - j/s);

dp[i+1][j]，新的bug不屬於已有的i個子集但屬於已有的j個分類，概率為(1-i/n)*j/s;

dp[i+1][j+1]，新的bug不屬於已有的i個子集也不屬於已有的j個分類，概率為(1 - i/n) * (1 - j/s)；

因此dp[i][j] = i/n*j/s*dp[i][j] + i/n * (1 - j/s)*dp[i][j+1] + (1-i/n)*j/s*dp[i+1][j] + (1 - i/n) * (1 - j/s)*dp[i+1][j+1] + 1。

#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#define LL __int64
#define LL long long
#define eps 1e-12
#define PI acos(-1.0)
using namespace std;
const int INF = 0x3f3f3f3f;
const int maxn = 4010;
double dp[1010][1010];

int main()
{
	int n,s;
	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;
				dp[i][j] = (dp[i+1][j]*(n-i)*j + dp[i][j+1]*i*(s-j) + dp[i+1][j+1]*(n-i)*(s-j)+n*s)/(n*s - i*j)*1.0;
			}
		}
		printf(%.4f
,dp[0][0]);
	}
	return 0;
}