ZOJ 3551 吸血鬼 概率DP

解题报告链接:

http://www.cnblogs.com/183zyz/archive/2012/09/13/2683524.html

做法:设当有i个吸血鬼时变成n个吸血鬼的天数的数学期望为dp[i].

pi为人和吸血鬼相遇的概率,pi = i*(n-i)/cn2 . cn2表示从n个人中选两个人出来的选法,那么人和吸血鬼相遇的选法为i*(n-i).p为人变吸血鬼的概率。

则有dp[i] = p*pi*(dp[i+1]+1)+(1-p*pi)(dp[i+1]+1)

化为:dp[i] = dp[i+1] + 1/(p*pi)

有dp[n] = 0;

很容易得到dp[1] = sum(1/(p*pi)) (1=<i<=n-1).

贴代码:

 #include<cstdio>
int main()
{
// freopen("in.c","r",stdin);
int t;
scanf("%d",&t);
while(t--)
{
int n;
double p;
scanf("%d%lf",&n,&p);
double s = (double)n*(n-)/;
double ans =;
for(int i=n-; i>=; --i)
{
double pi=(double)i*(n-i)/s;
ans += 1.0/(p*pi);
}
printf("%.3f\n",ans);
}
return ;
}
上一篇:System.getProperty()引起的悲剧--您的主机中的软件中止了一个已建立的连接


下一篇:Struts2中ActionContext和ServletActionContext