UVA 11427 Expect the Expected (概率dp+推公式求期望 详解)

时间:2021-02-13 08:12:47

题目链接:https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2422


题目大意:一个人每天玩游戏,玩一局胜利的概率为p,一天最多玩n次,如果当天某时刻胜率大于p则结束,第二天继续玩,如果某天玩了n次胜率还是不大于p,则失败不再玩,求玩的天数的期望


题目分析:先求一天失败的概率q,设dp[i][j]为一天内玩了i局胜j局的概率,则q=∑dp[n][i] (i / n <= a / b),下面是dp方程:

dp[i][0] = dp[i - 1][0] * (1- p),  一局都没胜利

dp[i][j] = dp[i - 1][j] * (1-  p),第i局输了

dp[i][j] = dp[i - 1][j - 1] * p,(a * i >= b * j),第i局胜了,这里一定要注意,前提是胜率不能大于p,否则当天就算胜利了

因为每天玩的情况都是独立的,最后答案E = 1 * q + 2 * q * (1 - q) + 3 * q * (1- q)^2 + ... + n * q * (1 - q)^(n - 1)  (n -> ∞)

E/q = 1 + 2 * (1 - q) + 3 * (1 - q)^2 + ... + n * (1 - q)^(n - 1)     ......(1)

E/q * (1 - q) = (1 - q) + 2 * (1 - q)^2 + 3 * (1 - q)^3 + ... + n * (1 - q)^n    ......(2)

(1) - (2) = E = 1 + (1 - q) + (1 - q)^2 + (1 - q)^3 + ... + (1 - q)^(n - 1) - n * (1 - q)^n

好多博客写的都不对,虽然不影响答案,等比数列求完后面还有一项,所以最后

E = 1 / q - (1 - q)^n / q - n * (1 - q)^n,显然(1 - q)^n / q这个在n趋向于无穷大的时候是0,至于n*(1-q)^n,令x=1-q,则0 < x < 1,令k = 1 / x,则k > 1,原式等于n / (k ^ n),然后洛必达法则,得到它的极限为0,其实你也可以说指数增长的肯定比线性快,但是这样证更清晰吧,所以最后得到E = 1 / q,如此简单的式子。。。orz

#include <cstdio>
#include <cstring>
int const MAX = 105;
double dp[MAX][MAX];

int main()
{
    int T;
    scanf("%d", &T);
    for(int ca = 1; ca <= T; ca++)
    {
        memset(dp, 0, sizeof(dp));
        int a, b, n;
        scanf("%d/%d %d", &a, &b, &n);
        double p = (double)a / (double)b;
        dp[0][0] = 1.0;
        for(int i = 1; i <= n; i++)
        {
            dp[i][0] = dp[i - 1][0] * (1.0 - p);
            for(int j = 1; j <= n; j++)
            {
                dp[i][j] += dp[i - 1][j] * (1.0 - p);
                if(a * i >= b * j)
                    dp[i][j] += dp[i - 1][j - 1] * p;
            }
        }
        double ans = 0;
        for(int i = 0; i <= n; i++)
            ans += dp[n][i];
        printf("Case #%d: %d\n", ca, (int) (1.0 / ans));
    }
}