洛谷 UVA11021 Tribles
2024-08-30 09:06:01
UVA11021 Tribles
题意翻译
题目大意
一开始有kk种生物,这种生物只能活1天,死的时候有p_ipi的概率产生ii只这种生物(也只能活一天),询问m天内所有生物都死的概率(包括m天前死亡的情况)
输入格式
第一行输入一个整数TT,表示数据总数
每一组先输入三个整数n(1<=n<=1000),k(0<=k<=1000),m(0<=m<=1000)n(1<=n<=1000),k(0<=k<=1000),m(0<=m<=1000)
然后输入n个整数,分别为p_0p0到p_{n-1}pn−1
输出格式
对于每一组数据,先输出"Case #x: " 再输出答案,精度要求在1e-6以内
感谢@xMinh 提供翻译
题目描述
输入格式
输出格式
输入输出样例
输入 #1复制
4
3 1 1
0.33
0.34
0.33
3 1 2
0.33
0.34
0.33
3 1 2
0.5
0.0
0.5
4 2 2
0.5
0.0
0.0
0.5
输出 #1复制
Case #1: 0.3300000
Case #2: 0.4781370
Case #3: 0.6250000
期望dp QAQ
就是说一共有k种生物 (他们之间是互斥的 不会互相影响)
笔记插入↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑↑
官方讲解:
/*
假设我们一开始只有一只麻球,它第i天所有后代都死亡的概率是f[i] 那么f[i] = p0 + p1*f[i-1] + p2*f[i-1]^2 + ...pn-1*f[i - 1]^(n-1) 也就是用前一天的全部死亡概率来代替今天的每一只死亡的概率, 又因为今天的每只的生死概率什么的都是独立的, 所以p2*f[i-1]^2可以理解成剩下2只, 然后两只都死了, 这样最后在第m天死光的概率就是f[m], 但是这个只是一只麻球的, 所有麻球都死光是f[m]^k
*/
/***步入正题***/
我们再来重新梳理一遍:
这一道题要求的是什么?
m天内 所有的生物都死的概率(包括m天前死的情况)
那我们可以先针对每一种生物来看待
f[i]表示i天内这种生物及其后代灭绝
1:f[m]
k:f[m]^k 因为它们是互不干扰的
那么如何来递推f[m]?我们来一个一个往下推一下试一试
f[0]=0
f[1]=p0
那么f[i] = p0 + p1*f[i-1] + p2*f[i-1]^2 + ...pn-1*f[i - 1]^(n-1)
然后那个几次方就是因为 那生2个来举例 生出来的两只是互不干扰的 所以要用次方
迷。。。所以这一道题的正解就出来了
#include<bits/stdc++.h>
using namespace std;
const int maxn=;
double p[maxn],f[maxn];
int main()
{
int T;
scanf("%d",&T);
for(int kk=;kk<=T;kk++)
{
int n,k,m;
scanf("%d%d%d",&n,&k,&m);
printf("Case #%d: ",kk);
for(int i=;i<n;i++)
scanf("%lf",&p[i]);
for(int i=;i<=m;i++)
{
f[i]=p[];
for(int j=;j<n;j++)
f[i]+=p[j]*pow(f[i-],j);
}
printf("%.7lf\n",pow(f[m],k));
} return ;
}
最新文章
- Windows系统上安装多个版本jdk,修改环境变量不生效
- java 面向对象编程--第十四章 多线程编程
- ZJOI2008泡泡堂BNB
- Calendar 类的应用
- IOS添加自定义字体库
- MongoDB学习笔记03
- 通过属性集名称获取属性集id
- uva 10003 Cutting Sticks (区间dp)
- Spring MVC 返回json数据 报406错误 问题解决方案
- Learning
- Taro音频createVideoContext组件无法调用方法
- 第75节:Java的中的JSP,EL和JSTL
- Ionic-轮播图ion-slide-box
- “Java是编译执行的语言”这句话对吗?
- python中的 set 中的元素
- 时间序列(六): 炙手可热的RNN: LSTM
- XML文件解析-SaxReader
- hdu 5696 区间的价值
- Intellij Idea上Spring Boot编译报错:Error:(3, 32) java: 程序包org.springframework.boot不存在
- [转载]利用近场探头和频谱仪查找EMI辐射问题
热门文章
- const(每个对象中的常量), static const(类的编译时常量)
- ZOJ 1276 ";Optimal Array Multiplication Sequence";(最优矩阵链乘问题+区间DP)
- java 一个类加载器的高级问题分析
- linux 使用 /proc 文件系统
- 聚类——DBSCAN
- C# 性能分析 反射 VS 配置文件 VS 预编译
- jQuery---鼠标滚轮控制div横向滚动条左右移动
- ZR提高失恋测2(9.7)
- ZR7.17
- CSS兼容性问题的解决方式(更新中&#183;&#183;&#183;)