CF 518 D. Ilya and Escalator
Ilya got tired of sports programming, left university and got a job in the subway. He was given the task to determine the escalator load factor.
Let's assume that n people stand in the queue for the escalator. At each second one of the two following possibilities takes place: either the first person in the queue enters the escalator with probability p, or the first person in the queue doesn't move with probability (1 - p), paralyzed by his fear of escalators and making the whole queue wait behind him.
Formally speaking, the i-th person in the queue cannot enter the escalator until people with indices from 1 to i - 1 inclusive enter it. In one second only one person can enter the escalator. The escalator is infinite, so if a person enters it, he never leaves it, that is he will be standing on the escalator at any following second. Ilya needs to count the expected value of the number of people standing on the escalator after t seconds.
Your task is to help him solve this complicated task.
The first line of the input contains three numbers n, p, t (1 ≤ n, t ≤ 2000, 0 ≤ p ≤ 1). Numbers n and t are integers, numberp is real, given with exactly two digits after the decimal point.
Print a single real number — the expected number of people who will be standing on the escalator after t seconds. The absolute or relative error mustn't exceed 10 - 6.
1 0.50 1
0.5
1 0.50 4
0.9375
4 0.20 2
0.4 简单dp
dp(i,j)表示第i分钟时,有j个人进去的概率
期望=∑j*dp(t,j) 注意:递推的时候要分2种情况:
队列还有人,队列已经没有人
#include<cstdio>
#include<cstring>
#include<vector>
#include<iostream>
#include<algorithm>
#include<stack>
#include<queue> #define LL long long
#define ULL unsigned long long using namespace std; const int maxn=; double dp[maxn][maxn]; void solve(int ,double ,int ); int main()
{
//loop:
int n,t;
double pro;
scanf("%d %lf %d",&n,&pro,&t);
solve(n,pro,t);
//goto loop;
return ;
} void solve(int n,double pro,int t)
{
for(int i=;i<maxn;i++)
for(int j=;j<maxn;j++)
dp[i][j]=0.0;
dp[][]=1.0; for(int i=;i<=t;i++){
dp[i][]=dp[i-][]*(1.0-pro);
for(int j=;j<=i;j++){
if(j<n){
dp[i][j]=dp[i-][j-]*pro+dp[i-][j]*(1.0-pro);
}
else if(j==n)
dp[i][j]=dp[i-][j-]*pro+dp[i-][j];
else
dp[i][j]=0.0;
}
} double ret=0.0;
for(int j=;j<=t;j++){
ret+=dp[t][j]*j;
} printf("%.10f\n",ret);
return ;
}
最新文章
- RSA密钥生成与使用
- Android Studio Jni 环境搭建
- Key-Vlaue Coding Apple官方翻译
- TCP/IP简介
- linux安装MySQL5.7.13(二进制|源码)
- django - raw sql - 注意点!
- Hadoop集群(第5期)_Hadoop安装配置
- Wordpress prettyPhoto插件跨站脚本漏洞
- QT5.0.1在Windows下 出现QApplication: No such file or directory 问题的解决办法
- nginx+lua+redis构建高并发应用(转)
- client多线程
- [WF4.0 现实] WF4.0 Receive &;amp;&;amp; Send
- 消息中间件Client模块划分
- 大家好,我是ZCDHJ
- BZOJ_3398_[Usaco2009 Feb]Bullcow 牡牛和牝牛_组合数学
- 第五章Bookstrap
- Google 开发的、最好用、功能最强大的网页测速与网站性能分析工具
- scrapy 中间件
- 更新:在MAC上安装RN开发环境的步骤(全)
- git 查看提交历史