6.4 KiB
一、题目描述
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$。