POJ-2096 Collecting Bugs【機率dp】

題意:

一個軟體有s個子系統，會産生n種bug

某人每天發現一個bug,這個bug屬于一個子系統，屬于一個分類

每個bug屬于某個子系統的機率是1/s,屬于某種分類的機率是1/n。

問發現n種bug,每個子系統都發現bug的天數的期望。

E（i,j）表示發現i種bug，j個子系統出問題的期望。

E(i,j)有四個轉移狀态.

把右邊 E(i,j)往左移在整理公式就得到E(i,j)的表達式。

使E(n,s)=0.逆推式子得到E(0,0)就是答案‘

#include <stdio.h>
#include <algorithm>
using namespace std;
const int maxn=1008;
const double eps=1E-8;
double e[maxn][maxn];
int s,n;
void DP()
{
	e[n][s]=0;
	for(int i=n;i>=0;--i)
		for(int j=s;j>=0;--j)
		{
			if(i==n&&j==s) continue;
			e[i][j]=((n-i)*(s-j)*e[i+1][j+1]+i*(s-j)*e[i][j+1]+(n-i)*j*e[i+1][j]+n*s)/(n*s-i*j);
		}
	printf("%.4f\n",e[0][0]);
}
int main()
{
	while(~scanf("%d%d",&n,&s))
	{
		DP();
	}
	return 0;
}