首页 > 其他 > 详细

POJ - 2096 Collecting Bugs(概率dp)

时间:2018-08-19 22:57:06      阅读:189      评论:0      收藏:0      [点我收藏+]

 

https://vjudge.net/problem/POJ-2096

题意

 一个软件有s个子系统,会产生n种bug。某人一天发现一个bug,这个bug属于某种bug,发生在某个子系统中。求找到所有的n种bug,且每个子系统都找到bug,这样所要的天数的期望。需要注意的是:bug的数量是无穷大的,所以发现一个bug,出现在某个子系统的概率是1/s,属于某种类型的概率是1/n。

分析

dp[i][j]表示已经找到i种bug,并存在于j个子系统中,要达到目标状态的天数的期望。显然,dp[n][s]=0,因为已经达到目标了。而dp[0][0]就是我们要求的答案。
dp[i][j]状态可以转化成以下四种:
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 )= ( n*s + (n-i)*j*dp[i+1,j] + i*(s-j)*dp[i,j+1] + (n-i)*(s-j)*dp[i+1,j+1] )/( n*s - i*j )

需要对式子化简一下,不然精度似乎不够。。

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <stack>
#include <set>
#include <bitset>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define ms(a, b) memset(a, b, sizeof(a))
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define IOS ios::sync_with_stdio(0);cin.tie(0);
#define random(a, b) rand()*rand()%(b-a+1)+a
#define pi acos(-1.0)
const ll INF = 0x3f3f3f3f3f3f3f3fll;
const int inf = 0x3f3f3f3f;
const int maxn = 1e5+10;
const int maxm = 1e5+10;
const ll mod = 1e9+7;
double dp[1010][1010];
int main(){
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//    freopen("output.txt", "w", stdout);
#endif
    int n,s;
    scanf("%d%d",&n,&s);
    dp[n][s]=0.0;
    int ns=n*s;
    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][j]*(1.0*i*j/(n*s))+dp[i+1][j]*(1.0*(n-i)*j/(n*s))
//                    +dp[i][j+1]*(1.0*i*(s-j)/(n*s))+dp[i+1][j+1]*(1.0*(n-i)*(s-j)/(n*s))+1;
            dp[i][j] = ( ns + (n-i)*j*dp[i+1][j] + i*(s-j)*dp[i][j+1] + (n-i)*(s-j)*dp[i+1][j+1] )/( ns - i*j );
        }
    }
    printf("%.4f\n",dp[0][0]);
    return 0;
}

 

POJ - 2096 Collecting Bugs(概率dp)

原文:https://www.cnblogs.com/fht-litost/p/9503115.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!