【概率DP】poj2096Collecting Bugs

本文主要是介绍【概率DP】poj2096Collecting Bugs，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

/*
水水的概率DP：
定义数组dp(i, j)表示在j个子系统中有i种bug..要达到目标的期望；；；
其中，dp[n][s]为0，因为已经是目标状态，，dp[0][0]为最终的结果；；
----
分析,dp[i][j]可以达到下面的4种状态：
dp[i][j]    发现一个bug属于已经找到的i种bug和j个子系统中的期望
dp[i+1][j]  发现一个bug属于新的一种bug，但属于已经找到的j种子系统的期望
dp[i][j+1]  发现一个bug属于已经找到的i种bug，但属于新的子系统的期望
dp[i+1][j+1]发现一个bug属于新的一种bug和新的一个子系统的期望
----------------------------------------------------------------------------
以上每种状态的概率为：
p1 = i*j / (n*s) 
p2 = (n-i)*j / (n*s) 
p3 = i*(s-j) / (n*s) 
p4 = (n-i)*(s-j) / (n*s)
--------------------------------------------------------------------------
期望可以分为其子期望的加权和，权为子期望发生的概率。。。。。
E(aA+bB+...) = aE(A) + bE(B) +... 
dp[i,j] = p1*dp[i,j] + p2*dp[i+1,j] + p3*dp[i,j+1] + p4*dp[i+1,j+1] + 1; 
dp[i,j] = ( 1 + p2*dp[i+1,j] + p3*dp[i,j+1] + p4*dp[i+1,j+1] )/( 1-p1 )；；；；；；
*/
#include <iostream>
#include <cstdio>
#include <cstring>
#define INF 0x3f3f3f3fusing namespace std;const int MAXN = 1010;double dp[MAXN][MAXN];int main()
{int n, s;while(scanf("%d%d",&n, &s) != EOF){int all = n*s;dp[n][s] = 0.0;for(int i=n; i>=0; i--){for(int j=s; j>=0; j--){if(i == n && j == s)continue;dp[i][j] = (all + (n-i)*j*dp[i+1][j] + i*(s-j)*dp[i][j+1] + (n-i)*(s-j)*dp[i+1][j+1] )/(all - i*j);}}printf("%.4lf\n",dp[0][0]);}return 0;
}

这篇关于【概率DP】poj2096Collecting Bugs的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---