CF148D.Bagofmice[概率dp]

作者:网络    软件教程库   2020-05-19

题目链接:http://codeforces.com/problemset/problem/148/d

题目大意:一袋子里有w个白老鼠,b个黑老鼠;a和b轮流抓老鼠(不放回),谁先抓到白老鼠,谁win;因为b粗鲁,每次抓完一只老鼠,会跑出来一只;a first;

求a win的概率;

题目分析:

此类概率dp的状态比较固定,dp(i , j )表示当前状态awin的概率;

1: dp[i][0],a win的概率为 1;dp[0][j] 概率为 0;

2: dp[i][j]

如果a取白,概率为 i/(i#43;j),

如果a取黑,b取白,概率 0,

如果a取黑,b取黑,跑出黑 概率 1.0*j/(i#43;j)*(j-1.0)/(i#43;j-1.0)*(j-2.0)/(i#43;j-2)*dp[i][j-3]; //前提 :黑=3

如果a取黑,b取黑,跑出白 概率 1.0*j/(i#43;j)*(j-1.0)/(i#43;j-1.0)*i/(i#43;j-2)*dp[i-1][j-2]; //前提:白=1;黑=2

代码:

//author:acsorry
//result:yes
#includeiostream
#includecstdio
#includecstring
#includecmath
#includealgorithm
#includevector
#includestring
#includequeue
#includedeque
#includestack
#includemap
#includeset
#define inf 129
#define maxint 0x7fffffff
#define sup 0x80000000
#define mem(a,b) memset(a,b,sizeof(a))
using namespace std;

typedef long long ll;
const int n=1007;

double dp[n][n];

int main()
{
    int w,b;
    while(cinwb)
    {
        dp[0][0]=0;
        for(int i=1;i=w;i++) dp[i][0]=1.0;//只有白鼠
        for(int i=1;i=b;i++) dp[0][i]=0.0;//只有黑鼠

        for(int i=1;i=w;i++){
            for(int j=1;j=b;j++){
                dp[i][j]=1.0*i/(i+j);
                if(j=3)
                    dp[i][j]+=1.0*j/(i+j)*(j-1.0)/(i+j-1.0)*(j-2.0)/(i+j-2)*dp[i][j-3];
                if(j=2)
                    dp[i][j]+=1.0*j/(i+j)*(j-1.0)/(i+j-1.0)*i/(i+j-2)*dp[i-1][j-2];
            }
        }
        printf(%.9f\n,dp[w][b]);

    }
    return 0;
}



cf 148d. bag of mice[概率dp]

原文地址:http://blog.csdn.net/code_or_code/article/details/45424869

本文内容由软件教程库(原文链接:https://www.itjcku.com/9999/1091502.html)本站为各位整理

阅读全部内容


Tags:概率几率

返回首页



推荐内容

HDU-1846-BraveGame(巴什博弈)

题目传送:brave game 介绍: 巴什博奕(bash game): 首先我们来玩一个比较古老的报数游戏。a ...

HDU-2149-PublicSale(巴什博弈)

题目传送:public sale 思路:巴什博弈 ac代码: #include lt;cstdiogt; # ...

enum实现售卖机

首先 推荐一下google的代码风格 :https://google-styleguide.googlecode ...

批量添加用户

a、创建用户文件,因为添加的用户比较多,因此编写脚本创建一个用户文件user.txt #!/bin/ba ...

解决侧滑中ViewPager和SlidingMenu的滑动冲突

当我们在使用开源框架slidingmenu时,如果要是使用到viewpager,就会出现滑动冲突。 解决方案: }/** ...

shell打乱文件行

思路,产生一个随机数组,然后按按照数组的元素将文件中行的重新输出 1、随机数组的生成 看书的时候感觉很是简单。第 ...

编程之美2015初赛第二场AB

题目1 : 扑克牌 时间限制:2000ms 单点时限:1000ms 内存限制:256mb 描述 一副不含王的扑 ...

Java设计模式之单例模式(恶汉式和懒汉式)

/* * 单例模式: * 饿汉式:类一加载就创建对象 * 懒汉式:用的时候,才去创建对象 * 面试题:单例模式的 ...

Html简单介绍

1、html--- hypertext markup language 的缩写 --- 超文本 标记 语言. 这个技 ...

configure:error:youmustconfigureinaseparatebuilddirectory

configure glibc-2.14 时出现以下错误: [[email#160;protected] opt]# ...

kohana框架生成feed

创建feed feed::create()斱法用给定癿参数杢创建 rss戒者 atom feed。下面是可接叐癿参数。 ...

用USB安装linux

手边没有光驱,安装ubuntu可以用 linuxlive usb creator 2.9.3,在百度网盘里有的。http ...

一个复杂子查询SQL优化

select * from test.vmark vk where id in (select v.id ...

Java多线程中常见的几个问题

我们都知道,在java中要想实现多线程,有两种手段,一种是继续thread类,另外一种是实现runable接口。  1. ...

OracleDataIntegrator12c-CreatingaCollocatedAgent

http://www.oracle.com/webfolder/technetwork/tutorials/obe/fm ...

CompilingGCC5onOSX

compiling gcc 5 on os x */--> pre.src {backgro ...

查看Linux上MySQL版本信息

如果mysql是用rpm或者yum安装的,可用 #rpm -qa|grep mysql查看. 如: [[email#16 ...

《赢在测试2-中国软件测试专家访谈录》读书笔记

《赢在测试2-中国软件测试专家访谈录》读书笔记 2015-04-30 测试人物经历与观点 1.董杰 百度测试架构师 董杰 ...

Objective-C的KVC和KVO

字面意思分别是: kvc是指key value coding,键值编码。 kvo是指key value observin ...

20150502调试分析之使用gdb远程调试ARM开发板

20150502 调试分析之 使用gdb远程调试arm开发板 2015-05-02 lover雪儿 今天我们要学习 ...

限制Apache日志access.log文件大小

可以在apache的httpd.conf配置文件中配置apache自带的程序rotatelogs的功能。 rotate ...

UVa11561-GettingGold

题目:给你一个二维的地图,里面有陷阱‘t‘,金子‘g‘以及墙壁‘#‘,和普通的道路‘.‘,现在已知一个人在起点‘p‘; ...

configure:error:cannotcomputesuffixofobjectfiles:cannotcompile

centos 6.5下安装gcc-4.8.4 make的时候提示以下错误: configure: error: can ...

我读的第一本书《梦断代码》

一切都是兴趣所在,兴趣才是发展的动力,虽然我们在这个开发过程中不可否认的会遇到挫折、瓶颈,但我认为,地狱与天堂共存 ...

iOS中定时器NSTimer的使用

ios中定时器nstimer的使用 1、初始化 + (nstimer *)timerwithtimeinterval:( ...

数组遍历二叉

//任务二叉树遍历 void cmission::initmission(dword base) { cha ...

Oracle基础<1>--数据库设计

一:为什么需要使用数据库设计   数据库设计可以使数据库通过健壮的数据库结构 高效并且健康 的进行工作。 二.数据库设计 ...

LinuxShell之七函数应用

函数是什么?函数是一些命令的集合,使用一个名称做代表,称为函数名称。函数名称的命名规则和变量相同。一旦函数定义好了,执行 ...

SkillButton技能冷却

#pragmaonce #include"cocos2d.h" using_ns_cc; classskillbutto ...

sles11启用Xmanager

一:开启xmanager要满足一下2个条件:1.安装了gnome桌面环境,并且默认启动级别为52.ip地址为固定ip地址 ...


本网站部分内容来自互联网,版权归原作者所有,文章内容仅代表原作者个人观点。如有侵权请联系我们删除 电子邮件 itjcku@foxmail.com