扑克牌 - 期望dp
https://www.acwing.com/problem/content/220/
#include <bits/stdc++.h>
using namespace std;
const int N = 20, inf = 1e9;
double f[N][N][N][N][5][5];
int A, B, C, D;
double dfs (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 aa = a + (x == 1) + (y == 1);
int bb = b + (x == 2) + (y == 2);
int cc = c + (x == 3) + (y == 3);
int dd = d + (x == 4) + (y == 4);
if (aa >= A && bb >= B && cc >= C && dd >= D) return t = 0;
t = 1;
double fm = a + b + c + d + (bool)x + bool(y);
fm = 54 - fm;
if (fm <= 0) return t = inf;
if (a < 13) t += (13 - a) / fm * dfs (a + 1, b, c, d, x, y);
if (b < 13) t += (13 - b) / fm * dfs (a, b + 1, c, d, x, y);
if (c < 13) t += (13 - c) / fm * dfs (a, b, c + 1, d, x, y);
if (d < 13) t += (13 - d) / fm * dfs (a, b, c, d + 1, x, y);
//大小王没被翻出来4rr
if (!x) {
double dt = inf;
for (int i = 1; i < 5; i++) dt = min (dt, 1.0 / fm * dfs (a, b, c, d, i, y));
t += dt;
}
if (!y) {
double dt = inf;
for (int i = 1; i < 5; i++) dt = min (dt, 1.0 / fm * dfs (a, b, c, d, x, i));
t += dt;
}
return t;
}
int main () {
memset (f, -1, sizeof f);
cin >> A >> B >> C >> D;
double ans = dfs (0, 0, 0, 0, 0, 0);
if (ans > inf / 2) cout << "-1.000";
else cout << fixed << setprecision (3) << ans;
}