ZOJ 3551 Bloodsucker <概率DP>
2024-08-30 08:16:55
题目:http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3551
题意:开始有N-1个人和一个吸血鬼, 每天有两个生物见面,当人遇到吸血鬼时有p的概率变成吸血鬼,求全部变成吸血鬼所需要的时间的期望~
思路: 设dp[i] 为还有 i 个人时,有一人变成吸血鬼的期望时间, p[i]为还有 i 个人时,有人变成吸血鬼的概率,
那么p[i]= p*i(N-i)/(N*(N-1)/2)~ dp[i]=1/p[i];
由 E(X)=∑E(X=xi) 得 E[N]=∑dp[i]~
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = ;
double dp[N], p;
int T, n;
int main()
{
scanf("%d", &T);
while(T--){
scanf("%d%lf", &n, &p);
dp[n] = ;
for(int i = n - ; i; --i){
double pi = p * i * (n - i) * / n / (n - );
dp[i] = dp[i + ] + / pi;
}
printf("%.3lf\n", dp[]);
}
return ;
}
最新文章
- xamarin 学习
- Facade(外观)-对象结构型模式
- paip. 提升性能---hibernate的缓存使用 总结
- Python2.5-原理之模块
- Long-Short Memory Network(LSTM长短期记忆网络)
- Linux 休眠,挂起(待机),关机等几个命令的区别及如何实现;如何启用Ubuntu的休眠模式
- java利用zxing编码解码一维码与二维码
- Map Columns From Different Tables and Create Insert and Update Statements in Oracle Forms
- ie6 span 换行IE6中float:right换行问题的替代解决方案
- [原创]X-HDL 4.2安装与使用
- 博客七----tensorflow-gpu安装满满填坑
- .net core webapi 将localhost改成ip地址
- Linux 基础内容
- 使用 udev 高效、动态地管理 Linux 设备文件
- 文件和文件夹不存在的时候,FileSystemWatcher 监听不到文件的改变?如果递归地监听就可以了
- Java 中 Emoji 的正则表达式
- springMVC源码分析--HttpMessageConverter参数read操作(二)
- 可视化库-Matplotlib-Pandas与sklearn结合(第四天)
- pureMVC与strangeIoc框架对比
- 01、Windows Store APP 设置页面横竖屏的方法