python

6.4 KiB

Raw Permalink Blame History Unescape Escape

This file contains ambiguous Unicode characters that may be confused with others in your current locale. If your use case is intentional and legitimate, you can safely ignore this warning. Use the Escape button to highlight these characters.

##AcWing 218. 扑克牌

一、题目描述

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

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

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

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

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

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

注：从牌堆里面翻出来的牌的期望张数最少是多少？ 期望:用初等数学的语言去描述，就是平均值是多少。 Q:为什么会有最少的概念出现的呢？这个数量不是固定的吗？答：这是因为大王和小王可以被认为是其中四个花色中的某一种花色，这就导致产生了不同的事件。放到红桃里是一种事件，放到黑桃里是一种事件,...,这四个事件的期望不一定相同！选择就在大小王上，我们要选择一个期望张数最少的放法，问我们这个期望张数最小是多少。

###yxc经典语录

图中，点是状态表示，边是状态转移。理解：前一个题中，需要建图，建图完成后才能用图进行状态表示和状态转移，本题，状态表示和状态转移都是很明确的，不需要建图。总结：动态规划是精髓，建图与否是表象。

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

输入格式 输入仅由一行，包含四个用空格隔开的整数，A,B,C,D。

输出格式 输出需要翻开的牌数的期望值 E，四舍五入保留 3 位小数。

如果不可能达到输入的状态，输出 -1.000。

数据范围 0≤A,B,C,D≤15

输入样例：

1 2 3 4

输出样例：

16.393

二、题意分析

状态表示

f[a][b][c][d][x][y] : 当前已翻开状态下，还需翻开牌的数量 期望数。

a,b,c,d 为已翻开的各类牌 (黑红花片) 的数量
x,y代表大、小王的状态（0为未翻开，1代表已翻开且当做黑桃，以此类推）, 设 rst 为剩余牌的数量。

rst=54-a-b-c-d-(x!=0)-(y!=0)

若 a < 13，则当前抽到黑桃的贡献为

\frac{13−a}{rst} \times f[a+1][b][c][d][x][y]

其余花色同理。若小王被抽取，取可转移状态期望最小的一个进行状态转移，其贡献为:

\frac{1}{rst} \times \min_{1≤i≤4}f[a][b][c][d][i][y]

大王同理。

记忆化搜索求解，若无牌可抽仍未到达 a > = A \&\& b > = B \&\& c > = C \&\& d > = D 的终止状态，则期望为正无穷，代表不合法的状态。

三、实现代码

#include <bits/stdc++.h>
using namespace std;
const int N = 15;
const int INF = 0x3f3f3f3f;
double f[N][N][N][N][5][5];
int A, B, C, D;

// 如果大小王翻出来放1里，则a++,放2里b++,...
void add(int &a, int &b, int &c, int &d, int x) {
    if (x == 1) a++;
    if (x == 2) b++;
    if (x == 3) c++;
    if (x == 4) d++;
}

/*
功能：计算当前状态f(a,b,c,d,x,y)下的期望值
*/
double dfs(int a, int b, int c, int d, int x, int y) {
    // 记忆化搜索
    if (f[a][b][c][d][x][y] > 0) return f[a][b][c][d][x][y];

    // 递归出口：当前状态是否到达目标状态，目标状态的期望值是0
    int ta = a, tb = b, tc = c, td = d;                     // 抄出来
    add(ta, tb, tc, td, x), add(ta, tb, tc, td, y);         // 大王小王会改变四个花色的数量
    if (ta >= A && tb >= B && tc >= C && td >= D) return 0; // 如果条件全满足就是终止状态

    // 当前状态下的剩余牌数量
    int rst = 54 - ta - tb - tc - td;
    if (rst <= 0) return INF; // 还没有完成目标，没有剩余的牌了，无解

    // 当前状态可以向哪些状态转移
    double v = 1;
    if (a < 13) // 黑桃有剩余，可能选出的是黑桃
        v += dfs(a + 1, b, c, d, x, y) * (13 - a) / rst;
    if (b < 13) // 红桃有剩余，可能选出的是红桃
        v += dfs(a, b + 1, c, d, x, y) * (13 - b) / rst;
    if (c < 13) // 梅花有剩余，可能选出的是梅花
        v += dfs(a, b, c + 1, d, x, y) * (13 - c) / rst;
    if (d < 13) // 方块有剩余，可能选出的是方块
        v += dfs(a, b, c, d + 1, x, y) * (13 - d) / rst;

    // 如果小王没有被选出
    if (x == 0)
        v += min(min(dfs(a, b, c, d, 1, y), dfs(a, b, c, d, 2, y)), min(dfs(a, b, c, d, 3, y), dfs(a, b, c, d, 4, y))) / rst;

    // 如果大王没有被选出
    if (y == 0)
        v += min(min(dfs(a, b, c, d, x, 1), dfs(a, b, c, d, x, 2)), min(dfs(a, b, c, d, x, 3), dfs(a, b, c, d, x, 4))) / rst;

    return f[a][b][c][d][x][y] = v;
}

int main() {
    cin >> A >> B >> C >> D;

    double res = dfs(0, 0, 0, 0, 0, 0); // 四种花色、大小王都还没有被抽取

    if (res > INF / 2) // 因为是浮点数，不能用等号判断是不是相等，简单的办法就是INF/2
        puts("-1.000");
    else
        printf("%.3f\n", res);
    return 0;
}

`Q`:期望值为什么初始化为`1`?

f[v_i]: 从i卡牌状态到终点状态所需要的期望卡牌数

每次抽一张牌变到下个状态，所以每条路径的权值为1

\large f[v]=p_1×(f[v_1]+1)+p_2×(f[v_2]+1)+p_3×(f[v_3]+1)+…+p_k×(f[v_k]+1) = \\ 
\sum_{i=1}^{k}p_i+\sum_{i=1}^{k}p_i \times f[v_i]

因为v一定能到达下个局面，所以下个状态的概率和为1，这里的\large \displaystyle \sum_{i=1}^{k}p_i=1 那么就有：\displaystyle \large f[v]=1+\sum_{i=1}^{k}p_i \times f[v_i] 综上这里的f[v]可以初始化为1。

6.4 KiB Raw Permalink Blame History Unescape Escape