【Codeforces 105D】 Bag of mice
2024-08-31 06:29:06
【题目链接】
http://codeforces.com/contest/148/problem/D
【算法】
概率DP
f[w][b]表示还剩w只白老鼠,b只黑老鼠,公主胜利的概率,那么 :
1. 公主抓到白老鼠,概率为w/(w+b)
2. 公主抓到黑老鼠,那么龙也抓到黑老鼠,如果跑出来的老鼠是白颜色的,则概率为 : b / (w + b) * b / (w + b - 1) * w / (w + b - 2) * f[w-1][b-2]
否则,概率为 : b / (w + b) * (b - 1) / (w + b - 1) * (b - 2) / (w + b - 2) * f[w][b-3]
【代码】
#include<bits/stdc++.h>
using namespace std; int i,j,w,b;
double f[][]; double dp(int w,int b)
{
if (w < || b < ) return ;
if (f[w][b] != -) return f[w][b];
if (w == ) return f[w][b] = ;
if (w == && b == ) return f[w][b] = ;
f[w][b] = 1.0 * w / (w + b);
if (w >= && b >= ) f[w][b] += 1.0 * b / (w + b) * (b - ) / (w + b - ) * w / (w + b - ) * dp(w-,b-);
if (b >= ) f[w][b] += 1.0 * b / (w + b) * (b - ) / (w + b - ) * (b - ) / (w + b - ) * dp(w,b-);
return f[w][b];
} int main()
{ scanf("%d%d",&w,&b);
for (i = ; i <= w; i++)
{
for (j = ; j <= b; j++)
{
f[i][j] = -;
}
}
printf("%.9lf\n",dp(w,b)); return ;
}
最新文章
- 使用SignalR实现服务端消息推送
- 项 目 管 理 知 识 体 系 指 南 (PMBOK2008)
- VTK初学一,a Mesh from vtkImageData
- 快速排序,C语言实现
- jqGrid 各种参数 详解
- [转载] google mock cookbook
- mysql 选择性高
- Mysql的ssl主从复制+半同步主从复制
- appserv安装
- ZendFramework2 源码分析 init_autoloader.php
- linux下C++ STL hash_map的使用以及使用char *型变量作为Key值的一大“坑”
- THUSC2015
- Ruby学习-第二章
- NetFPGA-1G-CML Demo --- reference_router_nf1_cml
- luogu准备复习(学习)题单
- elixir 关键字列表
- [AT1999] [agc002_e] Candy Piles
- FastStoneCapture(FSCapture)录屏、剪辑教程
- 《Crafting Rails 4 Applications》的笔记-第28页
- [原创]Spring Boot + Mybatis 简易使用指南(二)多参数方法支持 与 Joda DateTime类型支持