题意
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;
}
标签:期望,红桃,int,扑克牌,黑桃,方块,include,放入,DP
From: https://www.cnblogs.com/miraclepbc/p/16600612.html