扑克牌（期望DP）

题意

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

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

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

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

题目链接：https://www.acwing.com/problem/content/220/

数据范围

\(0 \leq A, B, C, D \leq 15\)

思路

经典的期望DP。我们考虑DP数组的状态，很明显我们需要用四维分别表示摸到的黑桃、红桃、梅花、方块的数量。此外我们还需要用两维分别记录大小王的状态。

因此，我们定义\(f(a, b, c, d, x, y)\)表示目前已经有\(a\)张黑桃，\(b\)张红桃，\(c\)张梅花，\(d\)张方块，大王状态为\(x\)，小王状态为\(y\)的情况下，到达目标状态还需要翻开牌的期望张数。

其中\(x\)和\(y\)的取值有\(4\)种，\(0\)代表放入黑桃，\(1\)代表放入红桃，\(2\)代表放入梅花，\(3\)代表放入方块，\(4\)代表还没摸到。下面考虑转移方程式：

若摸到的牌是黑桃，那么转移到状态\(f(a + 1, b, c, d, x, y)\)，概率为\(p = \frac{13 - a}{54 - a - b - c - d - x \neq 4 - y \neq 4}\)。其他颜色的牌同理。

现在考虑，如果摸到的牌是大王。最优策略就是转移到期望值最小的那个状态，也就是\(\arg max_i f(a, b, c, d, i, y), i = 0, 1, 2, 3\)。小王同理。

记忆化搜索即可。

代码

#include <iostream>
#include <cstring>
#include <algorithm>
#include <cstdio>

using namespace std;

const int M = 15;
const double inf = 1e20;

int A, B, C, D;
double f[M][M][M][M][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 as = a + (x == 0) + (y == 0);
    int bs = b + (x == 1) + (y == 1);
    int cs = c + (x == 2) + (y == 2);
    int ds = d + (x == 3) + (y == 3);
    if(as >= A && bs >= B && cs >= C && ds >= D) {
        v = 0;
        return v;
    }
    int sum = a + b + c + d + (x != 4) + (y != 4);
    sum = 54 - sum;
    if(sum <= 0) {
        v = inf;
        return v;
    }
    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 t = inf;
        for(int i = 0; i < 4; i ++) {
            t = min(t, 1.0 / sum * dfs(a, b, c, d, i, y));
        }
        v += t;
    }
    if(y == 4) {
        double t = inf;
        for(int i = 0; i < 4; i ++) {
            t = min(t, 1.0 / sum * dfs(a, b, c, d, x, i));
        }
        v += t;
    }
    return v;
}

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