poj2096 概率dp入门

我就是我 2022-08-20 15:16 177阅读 0赞

题意：

一个系统有s个子系统，一共会产生n中bug。某人一天可以发现一个bug，这个bug属于一个子系统，属于一个种类，每个bug属于某个子系统的概率是1/s,属于某个分类的概率是1/n,问发现n种bug并且每个子系统都发现bug的天数的期望。

分析：

简单的入门概率dp，在这之前没有做个这个类型，所以讲解也是看的网上的，这里直接贴过来。

dp[i][j]表示已经找到i种bug,j个系统的bug，达到目标状态的天数的期望
             dp[n][s]=0;要求的答案是dp[0][0];
             dp[i][j]可以转化成以下四种状态:
                  dp[i][j],发现一个bug属于已经有的i个分类和j个系统。概率为(i/n)*(j/s);
                  dp[i][j+1],发现一个bug属于已有的分类，不属于已有的系统.概率为 (i/n)*(1-j/s);
                  dp[i+1][j],发现一个bug属于已有的系统，不属于已有的分类,概率为 (1-i/n)*(j/s);
                  dp[i+1][j+1],发现一个bug不属于已有的系统，不属于已有的分类,概率为 (1-i/n)*(1-j/s);
            整理便得到转移方程

PS：需要注意的是，递推公式一定要化简，不让会WA

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <algorithm>
    using namespace std;
    
    int const maxn = 1005;
    double dp[maxn][maxn];
    //dp[i][j]表示的是已经找到i种bug，并且属于j个系统的bug，达到目标状态的天数的期望
    //dp[n][s]=0，因为这时已经达到目标状态了，最终结果是dp[0][0]
    //dp[i][j] = (dp[i][j]*(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) ;
    
    int main()
    {
        int n,s;
        while(scanf("%d%d",&n,&s)!=EOF)
        {
            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) + s*n) /(n*s-i*j) ;
                }
            }
            printf("%.4f\n",dp[0][0]) ;
        }
        return 0;
    }