CF 518D（概率dp）

题意：有n个人排队进车厢，每秒只能进一个人，而且第1个人进了后面的人才能进，第一个人每秒进入车厢的概率为p，不进的概率为1-p，求t秒后进入车厢总人数的数学期望。

分析:设dp[i][j]表示第i秒进了j个人的概率，则：

dp[i][j]=dp[i-1][j]*(1-p)+dp[i-1][j-1]*p.

注意边界限制：

当j=0时：dp[i][j]=dp[i-1][j]*(1-p)

当j=n时：dp[i][j]=dp[i-1][j]+dp[i-1][j-1]*p.因为如果第i-1秒都进入n个人了，第i秒必定也已经进入n个人了。

#pragma comment(linker,"/STACK:1024000000,1024000000")

#include <cstdio>

#include <cstring>

#include <string>

#include <cmath>

#include <limits.h>

#include <iostream>

#include <algorithm>

#include <queue>

#include <cstdlib>

#include <stack>

#include <vector>

#include <set>

#include <map>

#define LL long long

#define mod 1000000007

#define inf 0x3f3f3f3f

#define eps 1e-6

#define N 2010

#define lson l,m,rt<<1

#define rson m+1,r,rt<<1|1

#define PII pair<int,int>

using namespace std;

inline LL read()

{

    char ch=getchar();LL x=,f=;

    while(ch>''||ch<''){if(ch=='-')f=-;ch=getchar();}

    while(ch<=''&&ch>=''){x=x*+ch-'';ch=getchar();}

    return x*f;

}

double dp[N][N];

int main()

{

    int n,t;

    double p;

    while(scanf("%d%lf%d",&n,&p,&t)>)

    {

        dp[][]=;

        for(int i=;i<=t;i++)

        {

            for(int j=;j<=n;j++)

                if(j>&&j<n)dp[i][j]=dp[i-][j]*(-p)+dp[i-][j-]*p;

                else if(j==n)dp[i][j]=dp[i-][j]+dp[i-][j-]*p;

                else dp[i][j]=dp[i-][j]*(-p);

        }

        double ans=;

        for(int i=;i<=n;i++)ans+=dp[t][i]*i;

        printf("%.10lf\n",ans);

    }

}

秒客网

CF 518D（概率dp）

相关文章