Expect the Expected UVA - 11427（概率dp）

时间：2021-08-29 06:53:48

题意：

　　每天晚上你都玩纸牌，如果第一次就赢了，就高高兴兴的去睡觉，如果输了就继续玩。假如每盘游戏你获胜的概率都为p，每盘游戏输赢独立。如果当晚你获胜的局数的比例严格大于p时才停止，而且每天晚上最多只能玩n局，如果获胜比例一直不超过p的话，以后就再也不玩纸牌了。问在平均情况下，你会玩多少个晚上纸牌。

解析：

　　求出一天的就完蛋的概率P，然后符合超几何分布，则期望的天数即为1/P

设dp[i][j]为前i次游戏 j次成功的概率  则 dp[i][j] = dp[i-1][j-1]*p + dp[i-1][j]*(1-p);

最后累加P = dp[n][1] + dp[n][2] + ```````  一直加到成功的次数除n 等于给出的p 即可

然后输出1/P

#include <iostream>

#include <cstdio>

#include <sstream>

#include <cstring>

#include <map>

#include <set>

#include <vector>

#include <stack>

#include <queue>

#include <algorithm>

#include <cmath>

#define rap(a, n) for(int i=a; i<=n; i++)

#define MOD 2018

#define LL long long

#define ULL unsigned long long

#define Pair pair<int, int>

#define mem(a, b) memset(a, b, sizeof(a))

#define _  ios_base::sync_with_stdio(0),cin.tie(0)

//freopen("1.txt", "r", stdin);

using namespace std;

const int maxn = , INF = 0x7fffffff;

double dp[][];

int main()

{

    int T, kase = ;

    cin>> T;

    while(T--)

    {

        mem(dp, );

        double a, b;

        int n;

        scanf("%lf/%lf%d", &a, &b, &n);

        double p = a/(double) b;

        dp[][] = , dp[][] = ;

        rap(, n)

        {

            for(int j=; j*b <= a*i; j++)   //等价于枚举满足j/i <= a/b 的j， 但避免了误差

            {

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

                if(j) dp[i][j] += dp[i-][j-] * p;  //防止越界

            }

        }

        double P = 0.0;

        for(int j=; j*b <= a*n; j++)

            P += dp[n][j];

        printf("Case #%d: %d\n", ++kase, (int)(/P));

    }

    return ;

}

相关文章