首页 > 代码库 > uva 11021 Tribles

uva 11021 Tribles

https://vjudge.net/problem/UVA-11021

 

k只麻球,每只活一天就死亡,临死之前可能会生成0——n-1只麻球

给出 生成i只麻球的概率p,

问m天后所有麻球都死亡的概率

 

令dp[i]表示1只麻球产生的后代在前i天死亡的概率

定义 pj * dp[i-1]^j 表示1只麻球产生了j个后代,他们全在前i-1天死亡

dp[i]= Σ  p j*dp[i-1]^j

ans=dp[m]^k

 

#include<cmath>#include<cstdio>#define N 1001#define rep(a,b,c) for(int a=c;a<=b;a++)using namespace std;double p[N],dp[N];int main(){    int t,n,k,m;    scanf("%d",&t);    int tt,i,j;    rep(tt,t,1)    {        scanf("%d%d%d",&n,&k,&m);        rep(i,n-1,0) scanf("%lf",&p[i]);        dp[1]=p[0];        rep(i,m,2)        {            dp[i]=0;            rep(j,n-1,0) dp[i]+=p[j]*pow(dp[i-1],j);        }        printf("Case #%d: %.7lf\n",tt,pow(dp[m],k));    }}

 

uva 11021 Tribles