$\text{AcWing}~218$.扑克牌

题目描述

Admin 生日那天，Rainbow 来找 Admin 玩扑克牌。

玩着玩着 Rainbow 觉得太没意思了，于是决定给 Admin 一个考验。

Rainbow 把一副扑克牌($54$ 张)随机洗开，倒扣着放成一摞。

然后 Admin 从上往下依次翻开每张牌，每翻开一张黑桃、红桃、梅花或者方块，就把它放到对应花色的堆里去。

Rainbow 想问问 Admin，得到 $A$ 张黑桃、$B$ 张红桃、$C$ 张梅花、$D$ 张方块需要翻开的牌的张数的期望值 $E$ 是多少？

特殊地，如果翻开的牌是大王或者小王，Admin 将会把它作为某种花色的牌放入对应堆中，使得放入之后 $E$ 的值尽可能小。

由于 Admin 和 Rainbow 还在玩扑克，所以这个程序就交给你来写了。

思路

一道概率期望 $\text{DP}$ 题。

设状态 $f_{a, b, c, d, x, y}$ 表示当前有 $a$ 张黑桃，$b$ 张红桃，$c$ 张梅花，$d$ 张方块，小王大王状态分别为 $x, y$（$= 0 \sim 3$ 分别表示放到了 $a, b, c, d$ 四堆中，$= 4$ 表示没有翻出来），从当前状态到目标 $A, B, C, D$ 的期望步数。

状态转移：

1. 假设当前摸到的是黑桃，要先判断是否满足 $a < 13$，若满足，则摸到黑桃的概率是 $\frac{13 - a}{sum}$（$sum$ 表示当前剩下几张牌没摸），可以转移到 $f_{a + 1, b, c, d, x, y}$ 状态。其他三种花色同理。
2. 假设当前摸到的是小王，摸到它的概率是 $\frac{1}{sum}$，只要枚举要把小王放到 $a, b, c, d$ 哪一堆里即可，若放到第 $i$ 堆，则可以转移到 $f_{a, b, c, d, i, y}$ 状态。大王同理。

使用记忆化搜索实现即可。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 20;
const double INF = 1e20;

int A, B, C, D;
double f[N][N][N][N][5][5];

double dfs(int a, int b, int c, int d, int x, int y)
{
    double &v = f[a][b][c][d][x][y];
    if (v >= 0) return v;
    int na = a + (!x) + (!y);
    int nb = b + (x == 1) + (y == 1);
    int nc = c + (x == 2) + (y == 2);
    int nd = d + (x == 3) + (y == 3);
    if (na >= A && nb >= B && nc >= C && nd >= D) return v = 0;
    int sum = a + b + c + d + (x != 4) + (y != 4);
    sum = 54 - sum;
    if (sum <= 0) return v = INF;
    v = 1;
    /*
    为什么这里初始化1？
    可以把 DP 数组放到图里，因为摸一张牌会到下一个状态，所以每条边长度为 1
    那么 f[i] = p[1] * (f[1] + 1) + p[2] * (f[2] + 1) + ... + p[k] * (f[k] + 1)
              = p[1] + p[2] + ... + p[k] + p[1] * f[1] + p[2] * f[2] + ... + p[n] * f[n]
    显然，p[1] + p[2] + ... + p[k] = 1，所以 v 要初始化 1
    */
    if (a < 13) v += (13.0 - a) / sum * dfs(a + 1, b, c, d, x, y);
    if (b < 13) v += (13.0 - b) / sum * dfs(a, b + 1, c, d, x, y);
    if (c < 13) v += (13.0 - c) / sum * dfs(a, b, c + 1, d, x, y);
    if (d < 13) v += (13.0 - d) / sum * dfs(a, b, c, d + 1, x, y);
    if (x == 4)
    {
        double mn = INF;
        for (int i = 0; i < 4; i ++ ) mn = min(mn, 1.0 / sum * dfs(a, b, c, d, i, y));
        v += mn;
    }
    if (y == 4)
    {
        double mn = INF;
        for (int i = 0; i < 4; i ++ ) mn = min(mn, 1.0 / sum * dfs(a, b, c, d, x, i));
        v += mn;
    }
    return v;
}

int main()
{
    scanf("%d%d%d%d", &A, &B, &C, &D);
    memset(f, -1, sizeof f);
    double res = dfs(0, 0, 0, 0, 4, 4);
    if (res > 60) res = -1.000;
    printf("%.3lf\n", res);
    return 0;
}