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
更多推荐
UVA11021 Trible
发布评论