首页 > 代码库 > 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(概率+递推)