睡前小dp-poj2096-概率dp

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

http://poj.org/problem?id=2096

有n种分类，s种子系统，相互独立。每天发现一个bug等概率的属于n种分类和s种子系统。

要使发现的bug完全覆盖n种分类，s种分类，求天数的期望值。

用dp[n][s]表示已发现n种分类s种子系统需要的天数期望，则

dp[n][s]可以转化成dp[n][s] dp[n+1][s] dp[n][s+1] dp[n+1][s+1]。

只要表示出每一种情况的概率就可以了。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

double dp[][];

int N,S;

int main()

{

    while(~scanf("%d%d",&N,&S))

    {

        dp[N][S] = ;

        for(int i=N;i>=;i--)

            for(int j=S;j>=;j--)

            {

                if(i==N&&j==S) continue;

                dp[i][j] = (i*(S-j)*dp[i][j+]+

                            (N-i)*j*dp[i+][j]+

                            (N-i)*(S-j)*dp[i+][j+]+

                            N*S)/(N*S-i*j);

            }

        printf("%.4f\n",dp[][]);

    }

}