ZOJ3551:Bloodsucker(概率DP)

题意：

最初由n-1个正常人和一个吸血鬼。每天会有两个人（把吸血鬼也算在内）见面。如果一个是吸血鬼，另一个是正常人，那么这个正常人有概率p会转变成吸血鬼。问你有多少天所有正常人都会变成吸血鬼，输出期望天数

题解：

倒推

设dp[i]表示：现在已经有i个吸血鬼，把剩下的人变成吸血鬼的概率。那么dp[n]=0

从n个人中选出来两个人有C²_n种选法，如果选择一个正常人另一个吸血鬼就有i*(n-i)种

所以选择一个正常人另一个为吸血鬼的概率为i*(n-i)/C_n²,我们把这个值设为ans

res=ans*p

dp[i]=dp[i+1]*res+dp[i]*(1-res)+1

因为dp[i]未知，所以把dp[i]移动到式子左边，化简一下即可

dp[i]=(dp[i+1]*res+1)/res

这概率题目输出都是double类型，在代码中加减乘除运算的时候可要注意了，要不然那里精度不够难办

代码：

#include<stdio.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<iostream>
using namespace std;
#define mem(a) memset(a,0,sizeof(a))
typedef long long ll;
const int maxn=100005;
const int INF=1e9;
const double blo=(1.0+sqrt(5.0))/2.0;
const double eps=1e-8;
double dp[maxn];
int main()
{
    int t,n;
    double p;
    scanf("%d",&t);
    while(t--)
    {
        mem(dp);
        scanf("%d%lf",&n,&p);
        for(int i=n-1;i>=1;--i)
        {
            double temp1=(double)n*(n-1.0)/2.0;
            double temp2=(double)i*(n-i);
            double p1=temp2/temp1*p;
            dp[i]=(dp[i+1]*p1+1.0)/p1;
            
        }
        printf("%.3lf
",dp[1]);
    }
    return 0;
}