CF518D. Ilya and Escalator [概率DP]

时间:2022-09-09 23:47:37

CF518D. Ilya and Escalator

题意:n个人,每秒p的概念队首的人进入电梯,求t秒后期望人数


直接使用期望定义

\(f[i][j]\) i秒后电梯中j个人的概率

注意n个人的时候直接\(f[i][n] \rightarrow f[i+1][n]\)

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
using namespace std;
typedef unsigned long long ll;
const int N=2005;
inline int read() {
char c=getchar(); int x=0, f=1;
while(c<'0' || c>'9') {if(c=='-')f=-1; c=getchar();}
while(c>='0' && c<='9') {x=x*10+c-'0'; c=getchar();}
return x*f;
} int n, t;
double p, f[N][N];
int main() {
freopen("in","r",stdin);
scanf("%d %lf %d", &n, &p, &t);
f[0][0]=1;
for(int i=0; i<t; i++) {
int lim = min(i, n-1);
f[i+1][n] += f[i][n];
for(int j=0; j<=lim; j++)
f[i+1][j+1] += f[i][j]*p, f[i+1][j] += f[i][j]*(1-p);
}
double ans=0;
for(int i=1; i<=n; i++) ans += i*f[t][i];
printf("%.7lf", ans);
}

CF518D. Ilya and Escalator [概率DP]的更多相关文章

  1. Codeforces Round &num;293 &lpar;Div&period; 2&rpar; D&period; Ilya and Escalator 概率DP

    D. Ilya and Escalator time limit per test 2 seconds memory limit per test 256 megabytes input standa ...

  2. CoderForces 518D Ilya and Escalator &lpar;期望DP&rpar;

    题意:给定 n 个人,在每一时刻一个人进入地铁的概率是 p,站着不动的概率是 1-p,然后问你 t 时间地铁里有多少人. 析:很明显这是一个期望DP,用d[i][j]表示 i 时刻 j 个人进入地铁的 ...

  3. &lbrack;题解&rsqb; &lbrack;CF518D&rsqb; Ilya and Escalator

    题面 题解 期望dp入门题 设\(f[i][j]\)为到\(i\)时间有\(j\)个人上了电梯的概率, 我们可以得到转移方程 \[ f[i][j]=\begin{cases}f[i-1][j]\cdo ...

  4. D&period; Ilya and Escalator

    D. Ilya and Escalator time limit per test 2 seconds memory limit per test 256 megabytes input standa ...

  5. CF 518D(概率dp)

    传送门:Ilya and Escalator 题意:有n个人排队进车厢,每秒只能进一个人,而且第1个人进了后面的人才能进,第一个人每秒进入车厢的概率为p,不进的概率为1-p,求t秒后进入车厢总人数的数 ...

  6. Codeforces 28C &lbrack;概率DP&rsqb;

    /* 大连热身D题 题意: 有n个人,m个浴室每个浴室有ai个喷头,每个人等概率得选择一个浴室. 每个浴室的人都在喷头前边排队,而且每个浴室内保证大家都尽可能均匀得在喷头后边排队. 求所有浴室中最长队 ...

  7. HDU 4405 Aeroplane chess &lpar;概率DP&rpar;

    题意:你从0开始,要跳到 n 这个位置,如果当前位置是一个飞行点,那么可以跳过去,要不然就只能掷骰子,问你要掷的次数数学期望,到达或者超过n. 析:概率DP,dp[i] 表示从 i  这个位置到达 n ...

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

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

  9. POJ 2151 Check the difficulty of problems &lpar;概率DP&rpar;

    题意:ACM比赛中,共M道题,T个队,pij表示第i队解出第j题的概率 ,求每队至少解出一题且冠军队至少解出N道题的概率. 析:概率DP,dp[i][j][k] 表示第 i 个队伍,前 j 个题,解出 ...

随机推荐

  1. Redis3&period;20阅读-SDS实现

    声明:这是本人参考黄建宏的<redis设计与实现>(源码版本是redis3.0)来学习redis3.20源码的笔记,如果有什么不对的地方,欢迎大家指正,大家一起学习.一起进步,QQ:499 ...

  2. &lbrack;windows操作系统&rsqb;目录和文件相关操作

    1.导出目录的树形结构到文本文件 tree /F d:\dir1 > d:\tree.txt 就是将d:\dir1的目录结构以树状形式输出报告到文件tree.txt中. 效果是这样的:

  3. jQuery中data&lpar;&rpar;方法用法实例

    语法结构一: 复制代码代码如下: $(selector).data(name,value) 参数列表: 参数 描述 name 存储的数据名称. value 将要存储的任意数据. 实例代码: 复制代码代 ...

  4. C语言柔性数组

    结构中最后一个元素允许是未知大小的数组,这个数组就是柔性数组.但结构中的柔性数组前面必须至少一个其他成员,柔性数组成员允许结构中包含一个大小可变的数组,sizeof返回的这种结构大小不包括柔性数组的内 ...

  5. 彻底删除oracle的方法

    环境:Windows 2000+ORACLE,其他环境类似 假设ORACLE安装路径为:D:\ORACLE ,其他路径操作类似 方法: 1.开始->设置->控制面板->管理工具-&g ...

  6. Ubuntu 14&period;10 下设置静态IP

    修改 /etc/network/interfaces 文件 sudo nano /etc/network/interfaces 修改为 # 前面的不变auto eth0 iface eth0 inet ...

  7. 转载&colon;rebar和erlang

    使用rebar生成erlang release 并进行热代码升级 http://blog.sina.com.cn/s/blog_6530ad590100wmkn.html 使用rebar工具开发erl ...

  8. Daily Scrum - 12&sol;02

    Meeting Minutes Shuo终于把文件存取弄好了!Wei大致把后端的代码整合好了,现在是可以基本实现算法的一个简易背单词版本.另外我们又交流了一下UI方面的事情,发现还是有一些问题(特别是 ...

  9. 自己封装jquery的一些方法 链式调用模式

    function getIndex(ele){ var parent=ele.parentNode; var brothers=parent.children; for(var i=0,len=bro ...

  10. 【Code&colon;&colon;Blocks】windows 环境下编译 Code&colon;&colon;Blocks(已修正)

    Code::Blocks 在2012-11-25发布了最新的12.11版本,相比上一个版本(10.05),Code::Blocks 进行了许多改进和更新(Change log). 引用 Wikiped ...