题目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4530
dp[i]表示现在存在i个吸血鬼要达成目标（全为吸血鬼）天数的数学期望
假如现在再增加一天，这一天可能会增加一个吸血鬼，
p1*（dp[i+1]+1）表示接下来的一天增加了一个吸血鬼，
所以为(dp[i+1]+1),
还有一种可能就是没有增加吸血鬼，概率自然是（1-p1）
dp[i]+1表示接下来的一天没有增加吸血鬼，但向后推移了一天
因此dp[i]这个状态可以转移到
dp[i+1]+1,概率为p1
dp[i]+1 概率为（1-p1）
所以dp[i]=(dp[i+1]+1)*p1+(dp[i]+1)*(1-p1);
p1是有i个吸血鬼再增加一个的概率
就是说一个人和一个吸血鬼相遇，且人成功变成吸血鬼的概率
为（n-i）*i*p/(C(n,2)),即2*(n-i)*i*p/((n-1)*n)
dp[i]=(dp[i+1]+1)*p1+(dp[i]+1)*p2
移项后化简得： p1*dp[i]=dp[i+1]*p1+1
1 #include <iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<cstdlib> 5 #include<stack> 6 #include<queue> 7 #include<iomanip> 8 #include<cmath> 9 #include<map> 10 #include<vector> 11 #include<algorithm> 12 using namespace std; 13 14 double d[110000]; 15 int main() 16 { 17 int i,j,t,n; 18 double p; 19 cin>>t; 20 while(t--) 21 { 22 cin>>n>>p; 23 d[n]=0; 24 for(i=n-1; i>=1; i--) 25 { 26 double s1,s2,p1; 27 s1=(double)n*(n-1)/2; 28 s2=(double)i*(n-i); 29 p1=s2/s1*p; 30 d[i]=(d[i+1]*p1+1)/p1; 31 } 32 printf("%.3lf\n",d[1]); 33 } 34 35 return 0; 36 }