題目：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=4530

dp[i]表示現(xiàn)在存在i個(gè)吸血鬼要達(dá)成目標(biāo)（全為吸血鬼）天數(shù)的數(shù)學(xué)期望
假如現(xiàn)在再增加一天，這一天可能會(huì)增加一個(gè)吸血鬼，
p1*（dp[i+1]+1）表示接下來的一天增加了一個(gè)吸血鬼，
所以為(dp[i+1]+1),
還有一種可能就是沒有增加吸血鬼，概率自然是（1-p1）
dp[i]+1表示接下來的一天沒有增加吸血鬼，但向后推移了一天
因此dp[i]這個(gè)狀態(tài)可以轉(zhuǎn)移到
dp[i+1]+1,概率為p1
dp[i]+1 概率為（1-p1）
所以dp[i]=(dp[i+1]+1)*p1+(dp[i]+1)*(1-p1);
p1是有i個(gè)吸血鬼再增加一個(gè)的概率
就是說一個(gè)人和一個(gè)吸血鬼相遇，且人成功變成吸血鬼的概率
為（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

移項(xiàng)后化簡(jiǎn)得： 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 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/bfshm/p/3279356.html

總結(jié)

以上是生活随笔為你收集整理的zoj 3351 Bloodsucker(概率 dp)的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。