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

题目链接：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));
    }
}