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 ;
}