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 提供翻译

题目描述

PDF

输入格式

输出格式

输入输出样例

输入 #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 ;
}

最新文章

  1. Windows系统上安装多个版本jdk,修改环境变量不生效
  2. java 面向对象编程--第十四章 多线程编程
  3. ZJOI2008泡泡堂BNB
  4. Calendar 类的应用
  5. IOS添加自定义字体库
  6. MongoDB学习笔记03
  7. 通过属性集名称获取属性集id
  8. uva 10003 Cutting Sticks (区间dp)
  9. Spring MVC 返回json数据 报406错误 问题解决方案
  10. Learning
  11. Taro音频createVideoContext组件无法调用方法
  12. 第75节:Java的中的JSP,EL和JSTL
  13. Ionic-轮播图ion-slide-box
  14. “Java是编译执行的语言”这句话对吗?
  15. python中的 set 中的元素
  16. 时间序列(六): 炙手可热的RNN: LSTM
  17. XML文件解析-SaxReader
  18. hdu 5696 区间的价值
  19. Intellij Idea上Spring Boot编译报错:Error:(3, 32) java: 程序包org.springframework.boot不存在
  20. [转载]利用近场探头和频谱仪查找EMI辐射问题

热门文章

  1. const(每个对象中的常量), static const(类的编译时常量)
  2. ZOJ 1276 &quot;Optimal Array Multiplication Sequence&quot;(最优矩阵链乘问题+区间DP)
  3. java 一个类加载器的高级问题分析
  4. linux 使用 /proc 文件系统
  5. 聚类——DBSCAN
  6. C# 性能分析 反射 VS 配置文件 VS 预编译
  7. jQuery---鼠标滚轮控制div横向滚动条左右移动
  8. ZR提高失恋测2(9.7)
  9. ZR7.17
  10. CSS兼容性问题的解决方式(更新中&#183;&#183;&#183;)