题目链接:?problemId=4530
BloodsuckerTime Limit:2 Seconds Memory Limit:65536 KB
In 0th day, there aren-1people and 1 bloodsucker. Every day, two and only two of them meet. Nothing will happen if they are of the same species, that is, a people meets a people or a bloodsucker meets a bloodsucker. Otherwise, people may be transformed into bloodsucker with probabilityp. Sooner or later(Ddays), all people will be turned into bloodsucker. Calculate the mathematical expectation ofD.
Input
The number of test cases (T,T≤ 100) is given in the first line of the input. Each case consists of an integernand a float numberp(1 ≤n< 100000, 0 <p≤ 1, accurate to 3 digits after decimal point), separated by spaces.
Output
For each case, you should output the expectation(3 digits after the decimal point) in a single line.
Sample Input12 1Sample Output1.000
题意:开始有 n-1个人,,1个吸血鬼,以后每天这 n 个中其中有两个会相遇,如果一个是吸血鬼,一个是人,那这个人有一定的概率 p 变成吸血鬼。
求这 n 个最后都变成吸血鬼所需天数的期望值。
PS:
用dp[i]来表示有 i 个吸血鬼时的期望值,dp[n]=0;
dp[1]即为所求。
dp[i] = d[i+1]*p3+d[i]*(1-p3)+1;
移项得:dp[i] = (dp[i+1]*p3+1)/p3;
代码如下:
#include <cstdio>#include <cstring>double dp[100017];int main(){int t, n;double p;scanf("%d",&t);while(t–){scanf("%d%lf",&n,&p);dp[n] = 0;double p1 = (double)n*(n-1)/2;//c n 2 n个人中选2人for(int i = n-1; i >= 1; i–){double p2 = (double)i*(n-i);double p3 = p2/p1*p;//相遇并变成吸血鬼的概率dp[i] = (dp[i+1]*p3+1)/p3;}printf("%.3lf\n",dp[1]);}return 0;}
却又小到连一粒嫉妒的沙石也不能容纳