基础数学算法-扑克牌

题目-扑克牌

在这里插入图片描述

问题分析

要求计算翻的牌的期望数量最少是多少, 因为大小王是可以作为任意一张牌加入到牌堆当中

假设定义状态 $f (a, b, c, d)$ 表示黑桃 $a$ 张, 红桃 $b$ 张, 梅花 $c$ 张, 方块 $d$ 张的状态
没办法表示大小王的决策状态, 也就是对于当前状态大小王是否使用过, 以及大小王加入到了哪个牌堆中

因此需要重新设计状态表示 $f (a, b, c, d, x, y)$ , 表示黑桃 $a$ 张, 红桃 $b$ 张, 梅花 $c$ 张, 方块 $d$ 张

$x = 0$ 表示放到 $a$ 中
$x = 1$ 表示放到 $b$ 中
$x = 2$ 表示放到 $c$ 中
$x = 3$ 表示放到 $d$ 中
$x = 4$ 表示当前牌未被翻出

这样就可以将当前局面的所有牌表示出来, 下一步问题是如何进行状态转移

因为翻出每个牌的概率是相等的, 可以分类讨论当前翻出的是哪张牌, 分为六种情况

当前使用过的牌的数量是 $s u m$
$\ne 4) + (y \ne 4)$
那么未翻开牌的数量是 $54 - s u m$

加入翻开的是黑桃, 下一张翻开是黑桃的概率是 $\frac{13 - a}{54 - sum}$ , 期望就是 $\frac{13 - a}{54 - sum} f(a + 1, b, c, d, x, y)$
红桃的概率是 $\frac{13 - b}{54 - sum} f(a, b + 1, c, d, x, y)$
梅花的概率是 $\frac{13 - c}{54 - sum} f(a, b, c + 1, d, x, y)$
方块的概率是 $\frac{13 - d}{54 - sum} f(a, b, c, d + 1, x, y)$

$f (a, b, c, d, 4, y)$ 状态转移到下一个状态, 翻开小王的情况需要进行决策, 有如下情况
$\min (\frac{1}{54 - sum} f(a + 1, b, c, d, 0, y), \frac{1}{54 - sum} f(a, b + 1, c, d, 1, y), \frac{1}{54 - sum} f(a, b, c + 1, d, 2, y)), \frac{1}{54 - sum} f(a, b, c, d + 1, 3, y)$

算法步骤

因为该问题的状态数量很多, 建图不方便, 也就是没办法使用拓扑排序进行状态转移, 因此上述算法使用记忆化搜索实现

代码实现

注意: 如果当前使用的牌的数量超过了总和 $54$ , 那么该方案不成立直接返回 $+\infty$

#include <bits/stdc++.h>

using namespace std;

const int N = 15, M = 5;
const double INF = 1e18;

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 &t = f[a][b][c][d][x][y];
    if (t >= 0) return t;

    int a_cnt = a + (x == 0) + (y == 0);
    int b_cnt = b + (x == 1) + (y == 1);
    int c_cnt = c + (x == 2) + (y == 2);
    int d_cnt = d + (x == 3) + (y == 3);
    if (a_cnt >= A && b_cnt >= B && c_cnt >= C && d_cnt >= D) return t = 0;

    int sum = a + b + c + d + (x != 4) + (y != 4);
    sum = 54 - sum;

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

    return t;
}

int main() {
   
    ios::sync_with_stdio(false);
    cin.tie(0);

    memset(f, -1, sizeof f);
    cin >> A >> B >> C >> D;

    double ans = dp(0, 0, 0, 0, 4, 4);
    if (ans > INF || ans < 0) ans = -1;

    printf("%.3lf\n", ans);

    return 0;
}

基础数学算法-扑克牌

目录

题目-扑克牌

问题分析

算法步骤

代码实现