题意
有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的更多相关文章
-
poj 2096 Collecting Bugs(期望 dp 概率 推导 分类讨论)
Description Ivan is fond of collecting. Unlike other people who collect post stamps, coins or other ...
-
POJ 2096 Collecting Bugs:期望dp
题目链接:http://poj.org/problem?id=2096 题意: 有一个程序猿,他每天都会发现一个bug. bug共有n个种类.属于某一个种类的概率为1/n. 有s个子系统,每个bug属 ...
-
POJ 2096 Collecting Bugs (概率DP,求期望)
Ivan is fond of collecting. Unlike other people who collect post stamps, coins or other material stu ...
-
Poj 2096 Collecting Bugs (概率DP求期望)
C - Collecting Bugs Time Limit:10000MS Memory Limit:64000KB 64bit IO Format:%I64d & %I64 ...
-
poj 2096 Collecting Bugs 概率dp 入门经典 难度:1
Collecting Bugs Time Limit: 10000MS Memory Limit: 64000K Total Submissions: 2745 Accepted: 1345 ...
-
poj 2096 Collecting Bugs (概率dp 天数期望)
题目链接 题意: 一个人受雇于某公司要找出某个软件的bugs和subcomponents,这个软件一共有n个bugs和s个subcomponents,每次他都能同时随机发现1个bug和1个subcom ...
-
poj 2096 Collecting Bugs - 概率与期望 - 动态规划
Ivan is fond of collecting. Unlike other people who collect post stamps, coins or other material stu ...
-
POJ 2096 Collecting Bugs (概率DP)
题意:给定 n 类bug,和 s 个子系统,每天可以找出一个bug,求找出 n 类型的bug,并且 s 个都至少有一个的期望是多少. 析:应该是一个很简单的概率DP,dp[i][j] 表示已经从 j ...
-
POJ 2096 Collecting Bugs 期望dp
题目链接: http://poj.org/problem?id=2096 Collecting Bugs Time Limit: 10000MSMemory Limit: 64000K 问题描述 Iv ...
随机推荐
-
maven常用插件: 打包源码 / 跳过测试 / 单独打包依赖项
一.指定编译文件的编码 maven-compile-plugin <plugin> <groupId>org.apache.maven.plugins</groupId& ...
-
使用StarUML创建类图
使用StarUML创建类图 http://www.flyne.org/article/379 1.综述(What) StarUML是一种生成类图和其他类型的UML图表的工具.本文是一个使用StarUM ...
-
浅谈android的selector,背景选择器
shape和selector的结合使用 (2013-04-07 11:11:00) 转载▼ 分类: android 1.Shape (1)作用:XML中定义的几何形状 (2)位置:res/draw ...
-
Android padding和margin的区别
如: Padding 为内边框,指该控件内部内容,如文本/图片距离该控件的边距 Margin 为外边框,指该控件距离边父控件的边距 如: 当按钮分别设置以上两个属性时,得到的效果是不一样的. andr ...
-
Nginx各版本的区别
Nginx官网提供了三个类型的版本Mainline version:Mainline 是 Nginx 目前主力在做的版本,可以说是开发版Stable version:最新稳定版,生产环境上建议使用的版 ...
-
记一次-angular-数字格式化
一个收费功能模块,需要做数据验证. input标签的ng-model的数据格式化 <input type="number" class="form-control& ...
-
Intent Flag实际项目 -- 超时跳转登录界面并清理前面所有activity
项目中涉及到登录超时跳转登录界面的逻辑,我以前的跳转flag为Intent.FLAG_ACTIVITY_CLEAR_TOP,但是点击返回按钮还是会回到上个界面.代码如下: ActivityUtils. ...
-
golang中使用ETCD
安装 下载ETCD https://github.com/etcd-io/etcd/releases/ 安装 我下载的是window版,直接解压就可以了,解压后有以下目录 点击etcd.exe运行 然 ...
-
webpack4.0
1. webpack 刚开始是js的模块打包,现在是一个任何模块打包工具 可以识别 CommonJS引入规范 CMD AMD 2. commonJS: module.exports r ...
-
oracle_18c新建用户用normal登陆失败
工具介绍:win10系统,使用的是oracle18c. 首先说一下oracle18c的特性,在oracle18c创建用户要以c##开头,比如: --创建新用户create user c##test_u ...