?

先说一下cf148D的题意：有一条龙与一位王妃进行比赛。一个袋子里装有m只白老鼠b只黑老鼠，王妃与龙轮流从中摸一只老鼠，先摸到白老鼠的是赢家（王妃是先手），但是，龙摸老鼠的时候会惊吓到其余的老鼠，会有一只老鼠从中自己跳出来（跳出来的老鼠如果是白色，不算任何人赢）。如果袋子里没有老鼠时还没有决出胜负算龙胜。

?

dp[i][j]表示王妃的胜率。

很明显dp[i][0](i > 0) = 1（只有白老鼠，王妃肯定赢）

dp[0][j] = 0（只有黑老鼠根据题意龙赢）

dp[i][j]可以转移到4个地方

1.王妃摸到白老鼠（赢）概率 1.0 * i / (i + j)

2.王妃摸到白老鼠，龙摸到黑老鼠（输）概率1.0 * j / (i + j) * 1.0 * i / (i + j - 1)

3.王妃摸到黑老鼠，龙摸到黑老鼠，跳出来一只白老鼠（可能赢）概率1.0 * j / (i + j) * 1.0 * (j - 1) / (i + j - 1) * 1.0 * i / (i + j - 2)

4.王妃摸到黑老鼠，龙摸到黑老鼠，跳出来一只黑老鼠（可能赢）概率1.0 * j / (i + j) * 1.0 * (j - 1) / (i + j - 1) * 1.0 * (j - 2) / (i + j - 2)

所以王妃的胜率 = 第一种情况 + 第三种情况 * dp[i - 1][j - 2] + 第四种情况 * dp[i][j - 3]; （dp[i][j]可以转移到dp[i - 1][j - 2],dp[i][j - 3]，而dp[i - 1][j - 2],dp[i][j - 3]又表示在这种情况下的胜率，所以要加上）

?

        for (int i = 1; i <= n; i++) dp[i][0] = 1.0;
        for (int j = 0; j <= n; j++) dp[0][j] = 0;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 1; j <= m; j++)
            {
                dp[i][j] = 1.0 * i / (i + j);

                if (j >= 2)
                {
                    dp[i][j] += 1.0 * j / (i + j) * 1.0 * (j - 1.0) / (i + j - 1.0) * 1.0 * i / (i + j - 2.0) * dp[i - 1][j - 2];
                }
                if (j >= 3)
                {
                    dp[i][j] += 1.0 * j / (i + j) * 1.0 * (j - 1.0) / (i + j - 1.0) * 1.0 * (j - 2.0) / (i + j - 2.0) * dp[i][j - 3];
                }
            }
        }

?

那么E1 = E1 * p1 + E2 * p2 + E3 * p3 + 2 (每次操作消耗2点法力)

为什么上面的等式成立，假如现在知道了E1， E2， E3的期望，而E1转移到这三个地方的概率也知道p1， p2， p3,那么根据期望的定义，加上本次操作2点法力值，就是上面的等式，可以将后面的E1， E2， E3看作随机变量X1, X2, X3。

?

等式化解后可以得到E1 = (E2 * p2 + E3 * p3) / (1 - p1) (1 - p1 != 0);

?

?

        for (int i = n; i >= 1; i--)
        {
            for (int j = m; j >= 1; j--)
            {
                if (i == n && j == m) continue;
                if (1.0 - temp[i][j][0] < eps) continue;
                dp[i][j] = (dp[i][j + 1] * temp[i][j][1] + dp[i + 1][j] * temp[i][j][2] + 2.0) / (1.0 - temp[i][j][0]);
            }
        }

?

?

        for (int i = n; i >= 0; i--)
        {
            if (i == n) continue;
            int p = i;

            while (mt[p]) p = mt[p];
            double temp = 0;

            if (p != i) dp[i] = dp[p];
            else
            {
                for (int j = 1; j <= 6; j++)
                {
                    if (p + j <= n)
                    {
                        temp += 1.0 / 6.0 * dp[p + j];
                    }
                }

                dp[i] = temp + 1.0;
            }
        }

?

?