【POJ 2096】Collecting Bugs 概率期望dp

时间:2022-05-06 05:01:35

有s个系统,n种bug,小明每天找出一个bug,可能是任意一个系统的,可能是任意一种bug,即是某一系统的bug概率是1/s,是某一种bug概率是1/n。

求他找到s个系统的bug,n种bug,需要的天数的期望。

分析

计算期望E=∑所有可能需要的天数*概率

找到s个系统n种bug,需要最少max(s,n)天,而可能的天数是无穷的,这样计算很复杂,复杂到算不了。

所以考虑dp,期望E=∑(昨天可以转移到现在状态的所有可能的情况的期望+1)*概率=∑(昨天可以转移到现在状态的所有可能的情况的期望)*概率 +1

一开始我想用dp[i][j]表示已经找到i种bug,j个系统里找到bug,的期望天数,但是这样不能推出来,由【i-1,j】【i,j-1】【i,j】【i-1,j-1】四种状态推的话,需要1天的概率我们知道,但是这四种情况的概率加起来不等于1,也就是还有需要2天3天...的情况,概率很复杂计算更复杂(回到上面的复杂去了)

所以要dp[i][j]表示已经找到i种bug,j个系统里找到bug,离目标还需要的期望天数。

好,如果明天找到一个bug。

它就可以转移到这里:

dp[i+1][j]  不属于i种,属于j个系统之一。  概率为p1=(n-i)/n* j/s 。

dp[i][j+1]  属于i种之一,不属于j个系统。    概率为p2=(s-j)/s* i/n

dp[i+1][j+1]  不属于i种,不属于j个系统。     概率为p3=(n-i)/n*(s-j)/s

dp[i][j]      属于i种之一,属于j个系统之一。  概率为p4=i/n* j/s

也就是比如找到了新种类,已知系统的bug,那明天离到达目标的期望天数就是dp[i+1][j],那就是今天还差dp[i+1][j]+1天。

dp[i][j]就是它找到的没有用的bug,那明天浪费了,那今天还差dp[i][j]+1天。今天和明天的dp[i][j]是一样的。

p1+p2+p3+p4=1,所以有下面这个式子。

dp[i][j]=dp[i+1][j]*p1+dp[i][j+1]*p2+dp[i+1][j+1]*p3+dp[i][j]*p4 +1

移项然后变成这样:dp[i][j]= ( 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 )

我们知道dp[n][s]=0,就是已经到达目标,还需要0天。然后逆推。

代码

#include<cstdio>
#define N 1005
double d[N][N];
int main()
{
int n,s;
scanf("%d%d",&n,&s);
for(int i=n; i>=; i--)
for(int j=s; j>=; j--)
{
if(i!=n||j!=s)
d[i][j]=(d[i+][j]*(n-i)*j+d[i][j+]*i*(s-j)+d[i+][j+]*(n-i)*(s-j)+n*s)/(n*s-i*j);
}
printf("%.4f",d[][]);
return ;
}

  

【POJ 2096】Collecting Bugs 概率期望dp的更多相关文章

  1. poj 2096 Collecting Bugs(期望 dp 概率 推导 分类讨论)

    Description Ivan is fond of collecting. Unlike other people who collect post stamps, coins or other ...

  2. POJ 2096 Collecting Bugs:期望dp

    题目链接:http://poj.org/problem?id=2096 题意: 有一个程序猿,他每天都会发现一个bug. bug共有n个种类.属于某一个种类的概率为1/n. 有s个子系统,每个bug属 ...

  3. POJ 2096 Collecting Bugs &lpar;概率DP,求期望)

    Ivan is fond of collecting. Unlike other people who collect post stamps, coins or other material stu ...

  4. Poj 2096 Collecting Bugs &lpar;概率DP求期望&rpar;

    C - Collecting Bugs Time Limit:10000MS     Memory Limit:64000KB     64bit IO Format:%I64d & %I64 ...

  5. poj 2096 Collecting Bugs 概率dp 入门经典 难度&colon;1

    Collecting Bugs Time Limit: 10000MS   Memory Limit: 64000K Total Submissions: 2745   Accepted: 1345 ...

  6. poj 2096 Collecting Bugs &lpar;概率dp 天数期望&rpar;

    题目链接 题意: 一个人受雇于某公司要找出某个软件的bugs和subcomponents,这个软件一共有n个bugs和s个subcomponents,每次他都能同时随机发现1个bug和1个subcom ...

  7. poj 2096 Collecting Bugs - 概率与期望 - 动态规划

    Ivan is fond of collecting. Unlike other people who collect post stamps, coins or other material stu ...

  8. POJ 2096 Collecting Bugs &lpar;概率DP&rpar;

    题意:给定 n 类bug,和 s 个子系统,每天可以找出一个bug,求找出 n 类型的bug,并且 s 个都至少有一个的期望是多少. 析:应该是一个很简单的概率DP,dp[i][j] 表示已经从 j ...

  9. POJ 2096 Collecting Bugs 期望dp

    题目链接: http://poj.org/problem?id=2096 Collecting Bugs Time Limit: 10000MSMemory Limit: 64000K 问题描述 Iv ...

随机推荐

  1. maven常用插件&colon; 打包源码 &sol; 跳过测试 &sol; 单独打包依赖项

    一.指定编译文件的编码 maven-compile-plugin <plugin> <groupId>org.apache.maven.plugins</groupId& ...

  2. 使用StarUML创建类图

    使用StarUML创建类图 http://www.flyne.org/article/379 1.综述(What) StarUML是一种生成类图和其他类型的UML图表的工具.本文是一个使用StarUM ...

  3. 浅谈android的selector,背景选择器

    shape和selector的结合使用 (2013-04-07 11:11:00) 转载▼   分类: android 1.Shape (1)作用:XML中定义的几何形状 (2)位置:res/draw ...

  4. Android padding和margin的区别

    如: Padding 为内边框,指该控件内部内容,如文本/图片距离该控件的边距 Margin 为外边框,指该控件距离边父控件的边距 如: 当按钮分别设置以上两个属性时,得到的效果是不一样的. andr ...

  5. Nginx各版本的区别

    Nginx官网提供了三个类型的版本Mainline version:Mainline 是 Nginx 目前主力在做的版本,可以说是开发版Stable version:最新稳定版,生产环境上建议使用的版 ...

  6. 记一次-angular-数字格式化

    一个收费功能模块,需要做数据验证. input标签的ng-model的数据格式化 <input type="number" class="form-control& ...

  7. Intent Flag实际项目 -- 超时跳转登录界面并清理前面所有activity

    项目中涉及到登录超时跳转登录界面的逻辑,我以前的跳转flag为Intent.FLAG_ACTIVITY_CLEAR_TOP,但是点击返回按钮还是会回到上个界面.代码如下: ActivityUtils. ...

  8. golang中使用ETCD

    安装 下载ETCD https://github.com/etcd-io/etcd/releases/ 安装 我下载的是window版,直接解压就可以了,解压后有以下目录 点击etcd.exe运行 然 ...

  9. webpack4&period;0

    1. webpack 刚开始是js的模块打包,现在是一个任何模块打包工具  可以识别 CommonJS引入规范     CMD AMD 2. commonJS:  module.exports   r ...

  10. oracle&lowbar;18c新建用户用normal登陆失败

    工具介绍:win10系统,使用的是oracle18c. 首先说一下oracle18c的特性,在oracle18c创建用户要以c##开头,比如: --创建新用户create user c##test_u ...