uva 11427 - Expect the Expected(概率)

题目大意：你每天晚上都会玩纸牌，每天固定最多玩n盘，每盘胜利的概率为p，你是一个固执的人，每天一定要保证胜局的比例大于p才会结束游戏，若n局后仍没有，就会不开心，然后以后再也不完牌，问说你最多会玩多少个晚上。

解题思路：当j/i ≤ p时有dp(i-1,j) (1-p) + dp(i-1, j-1)
p,其它dp(i,j) = 0.Q=∑d(n,i)

列出数学期望公式：

EX=Q+2Q(1−Q)+3Q(1−Q)2+…

s=EXQ=1+2(1−Q)+3(1−Q)2+…

(1−Q)∗s=(1−Q)+2(1−Q)2+3(1−Q)3+…

EX=Qs=1+(1−Q)+(1−Q)2+(1−Q)3…

为等比数列，依据等比数列求和公式，n趋近无穷大是为1/Q

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 105;

double dp[maxn][maxn];

int main () {

    int cas;

    scanf("%d", &cas);

    for (int kcas = 1; kcas <= cas; kcas++) {

        int a, b, n;

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

        double p = (double)a / b;

        memset(dp, 0, sizeof(dp));

        dp[0][0] = 1;

        dp[0][1] = 0;

        for (int i = 1; i <= n; i++) {

            for (int j = 0; j * b <= a * i; j++) {

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

                if (j)

                    dp[i][j] += dp[i-1][j-1] * p;

            }

        }

        double q = 0;

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

            q += dp[n][i];

        printf("Case #%d: %d\n", kcas, (int)(1/q));

    }

    return 0;

}

秒客网

uva 11427 - Expect the Expected(概率)

相关文章