poj 2096 Collecting Bugs(機率dp)

題意：Ivan每天能找到一個bug，現在有一個工程，有n種bug，s個子系統。問在這個工程中找出n種bug并且每個子系統至少有1個bug的天數的期望是多少。

思路：用dp[i][j]表示目前找出了i種bug，這些bug在j個子系統中，那麼再找一個bug可能的情況有下面幾種。

①找到的這個bug不在找到的i種bug中，但是在已經出現bug的j個子系統中。

②找到的這個bug在找到的i種bug中，但是不在已經出現bug的j個子系統中。

③找到的這個bug不在找到的i種bug中，并且不在已經出現bug的j個子系統中。

④找到的這個bug在找到的i種bug中，并且在已經出現bug的j個子系統中。

根據上面四種情況進行轉移。詳細看代碼~

代碼：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<algorithm>
#include<map>
#include<queue>
#include<stack>
#include<set>
#include<cmath>
#include<vector>
#define inf 0x3f3f3f3f
#define Inf 0x3FFFFFFFFFFFFFFFLL
#define eps 1e-9
#define pi acos(-1.0)
using namespace std;
typedef long long ll;
const int maxn=1000+10;
double dp[maxn][maxn];
bool flag[maxn][maxn];
int n,s;
double f(int x,int y)
{
    if(x==n&&y==s) return 0;
    if(x>n||y>s) return 0;
    if(flag[x][y]) return dp[x][y];
    flag[x][y]=true;
    dp[x][y]=f(x+1,y)*(n-x)/n*y/s+f(x,y+1)*x/n*(s-y)/s+1;
    dp[x][y]+=f(x+1,y+1)*(n-x)/n*(s-y)/s;
    dp[x][y]/=(1-(double)x*y/n/s);
    return dp[x][y];
}
int main()
{
    //freopen("in.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    while(~scanf("%d%d",&n,&s))
    {
        memset(flag,0,sizeof(flag));
        double ans=f(0,0);
        printf("%.4lf\n",ans);
    }
    return 0;
}