ZOJ.3551.Bloodsucker(期望DP)

題目鏈接

\(Description\)
有1個吸血鬼和n-1個人，每天有且只會有兩個人/吸血鬼相遇，如果是人與吸血鬼相遇，那個人會有p的概率變成吸血鬼；否則什么也不發生。求n個都變成吸血鬼的期望天數。

\(Solution\)
我還是寫一下吧。。期望題一般倒著遞推。
設\(f[i]\)為當前有\(i\)個吸血鬼，要變成\(n\)個吸血鬼的期望天數。那么\(f[n]=0\)，答案即\(f[1]\).
一天要么變一個要么不變，很好想到：
\[f[i]=p_i(f_{i+1}+1)+(1-p_i)(f_i+1)\]
\[p_i*f[i]=p_i*f[i+1]+1\]
\[f[i]=\frac{1}{p_i}+f[i+1]\]
而\[p_i=\frac{C(i,1)*C(n-i,1)}{C(n,2)}*p\]
那么\[f[i]=\frac{n*(n-1)}{2*i*(n-i)*p}+f[i+1]\]

#include <cstdio>int main()
{int T; scanf("%d",&T);long long n; double p,res;while(T--){scanf("%lld%lf",&n,&p), res=0;for(int i=n-1; i>=1; --i)res += 1.0*(n*(n-1))/(2.0*i*(n-i)*p);printf("%.3lf\n",res);}return 0;
}