首页 > 代码库 > Uva 11021-Tribles(概率+递推)
Uva 11021-Tribles(概率+递推)
题目链接:点击打开链接
题意:k只麻球,每活一天就会死亡,但第二天可能会生一些麻球,具体是 生i个麻球的概率为pi ,求m天后所有麻球都死亡的概率。
思路:考虑全概率公式,求k只麻球m天后全死亡 ,因为死亡是独立事件,应用乘法 ,ans= f[m] ^k ,f[m] 为一只麻球m天后均死亡的概率。对于第i天,
f[i]=p0+p1*f[i-1]^1 +p2*f[i-1]^2 +...p(n-1)*f[i-1]^(n-1) (就是让i-1天所有的出生的麻球全部死亡,那么第i天麻球就没了。。)
最终答案是 f[m]^k.
#include <algorithm> #include <iostream> #include <cstring> #include <cstdlib> #include <string> #include <cctype> #include <vector> #include <cstdio> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #define maxn 1<<12 #define _ll __int64 #define ll long long #define INF 0x3f3f3f3f #define Mod 1000000007 #define pp pair<int,int> #define ull unsigned long long using namespace std; double f[1002],p[1002]; int n,m,k; int main() { int T,cas=1; scanf("%d",&T); while(T--) { scanf("%d%d%d",&n,&k,&m); for(int i=0;i<n;i++) scanf("%lf",&p[i]); f[0]=0;f[1]=p[0]; for(int i=2;i<=m;i++) { f[i]=0; for(int j=0;j<n;j++) f[i]+=p[j]*pow(f[i-1],j); } printf("Case #%d: %.7lf\n",cas++,pow(f[m],k)); } return 0; }
Uva 11021-Tribles(概率+递推)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。