UVA11021 Trible

Trible"/>

UVA11021 Trible

UVA11021 Tribles

题目大意

一开始有 k 种生物，这种生物只能活1天，死的时候有 $p_i$的概率产生 i 只这种生物（也只能活一天），询问m天内所有生物都死的概率（包括m天前死亡的情况）

solution

概率DP水题 如果不会概率与期望的可以到我的博客my blog中查看。

显然对于每个生物m天全挂掉的概率一样，于是我们就只用考虑其中一只，另dp[i]为一只生物在i天后死掉的概率。

由全概率公式dp[i]=$\sum_{j=0}^{n-1}p[j]*dp[i-1]^j$


代码如下

#include<bits/stdc++.h>using namespace std;const int MAXN  = 1000+10;inline int read()
{int f=1,x=0;char ch;do{ch=getchar();if(ch=='-') f=-1;}while(ch<'0'||ch>'9');do{x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}while(ch>='0'&&ch<='9');return f*x;
}int t;
int n,m,k;
double dp[MAXN];
double p[MAXN];
int num=0;int main()
{t=read();while(t--){n=read();k=read();m=read();for(int i=0;i<n;i++) scanf("%lf",&p[i]);dp[0]=0;dp[1]=p[0];double sum;for(int i=2;i<=m;i++) {sum=1;dp[i]=0;for(int j=0;j<n;j++){dp[i]+=p[j]*sum;sum*=dp[i-1];   }}++num;printf("Case #%d: %.7f\n",num,pow(dp[m],k));}
} 

转载于:.html