UVA 11021 Tribles(递推+概率)

题目链接:http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=33059

【思路】

递推+概率。

设f[i]表示一只Tribble经过i天之后死绝的概率,则有递推式:

f[i]=p[0]+p[1]*(f[i-1]^1)+…p[n-1]*(f[i-1]^n-1)

最后答案为f[m]^k

【代码】

 #include<cstdio>
#include<cstring>
#define FOR(a,b,c) for(int a=(b);a<=(c);a++)
using namespace std; const int N = +; double p[N] , f[N];
int n,m,k; double pow(double x,int p) {
double ans=,tmp=x;
while(p) {
if(p&) ans*=tmp;
tmp*=tmp; p>>=;
}
return ans;
} int main() {
int T,kase=;
scanf("%d",&T);
while(T--) {
scanf("%d%d%d",&n,&k,&m);
FOR(i,,n-) scanf("%lf",&p[i]);
f[]=; f[]=p[];
FOR(i,,m) {
f[i]=;
FOR(j,,n-) f[i]+=p[j]*pow(f[i-],j);
}
printf("Case #%d: %.7lf\n",++kase,pow(f[m],k));
}
return ;
}
上一篇:leetcode旋转数组查找 二分查找的变形


下一篇:Scanner 与 Readable 的read()方法