扑克牌

AcWing-218-扑克牌

分析

见《进阶指南》第183页。

实现

#include <iostream>
#include <cstring>
using namespace std;

const int N = 15, M = 5;
const double inf = 1e20;
int A, B, C, D;
double f[N][N][N][N][M][M];

double dp (int a, int b, int c, int d, int x, int y) {
    double& cur = f[a][b][c][d][x][y];
    if (cur >= 0) return cur;

    int ca = a + (x == 0) + (y == 0);
    int cb = b + (x == 1) + (y == 1);
    int cc = c + (x == 2) + (y == 2);
    int cd = d + (x == 3) + (y == 3);
    if (ca >= A && cb >= B && cc >= C && cd >= D) return 0;

    // 剩下 sum 张牌
    int sum = 54 - (a + b + c + d + (x != 4) + (y != 4));
    if (sum <= 0) return inf;

    cur = 0;
    if (a < 13) cur += (13.0 - a) / sum * (dp(a + 1, b, c, d, x, y) + 1);
    if (b < 13) cur += (13.0 - b) / sum * (dp(a, b + 1, c, d, x, y) + 1);
    if (c < 13) cur += (13.0 - c) / sum * (dp(a, b, c + 1, d, x, y) + 1);
    if (d < 13) cur += (13.0 - d) / sum * (dp(a, b, c, d + 1, x, y) + 1);
    if (x == 4) {
        double min_exp = inf;
        for (int i = 0; i < 4; ++ i)
            min_exp = min(min_exp, 1.0 / sum * (dp(a, b, c, d, i, y) + 1));
        cur += min_exp;
    }
    if (y == 4) {
        double min_exp = inf;
        for (int i = 0; i < 4; ++ i)
            min_exp = min(min_exp, 1.0 / sum * (dp(a, b, c, d, x, i) + 1));
        cur += min_exp;
    }
    return cur;
}

int main () {
    memset(f, -1, sizeof(f)); // nan
    scanf("%d%d%d%d", &A, &B, &C, &D);

    double res = dp(0, 0, 0, 0, 4, 4);
    printf("%.3lf", res > 54 ? -1 : res);
    return 0;
}