双倍经验:AcWing 218. 扑克牌 ,标准的记忆化搜索+期望 DP ,题解略,直接看代码。
由于 AcWing 对 SPJ 设置的特殊性,-1
必须直接输出 -1
,不可以带小数点。
#include <stdio.h>
#include <string.h>
#include <algorithm>
const int N = 15;
const double INF = 1145141919810114514.0;
int T;
int A, B, C, D;
double dp[N][N][N][N][6][6];
// x,y : 0~3 seen as normal card 4 : undetermined
double dfs(int a, int b, int c, int d, int x, int y)
{
double& v = dp[a][b][c][d][x][y];
if (v >= 0.0) return v;
int ar = a + (x == 0) + (y == 0), br = b + (x == 1) + (y == 1);
int cr = c + (x == 2) + (y == 2), dr = d + (x == 3) + (y == 3);
if (ar >= A && br >= B && cr >= C && dr >= D) return v = 0;
int remain = 54 - (a + b + c + d + (x != 4) + (y != 4));
if (remain <= 0) return v = INF;
v = 1;
if (a < 13) v += dfs(a + 1, b, c, d, x, y) * (13.0 - a) / remain;
if (b < 13) v += dfs(a, b + 1, c, d, x, y) * (13.0 - b) / remain;
if (c < 13) v += dfs(a, b, c + 1, d, x, y) * (13.0 - c) / remain;
if (d < 13) v += dfs(a, b, c, d + 1, x, y) * (13.0 - d) / remain;
if (x == 4)
{
double joker = INF;
for (int i = 0; i < 4; ++i) joker = std::min(joker, dfs(a, b, c, d, i, y) * 1.0 / remain);
v += joker;
}
if (y == 4)
{
double Joker = INF;
for (int i = 0; i < 4; ++i) Joker = std::min(Joker, dfs(a, b, c, d, x, i) * 1.0 / remain);
v += Joker;
}
return v;
}
void solve(int t)
{
scanf("%d%d%d%d", &A, &B, &C, &D), memset(dp, -1, sizeof(dp));
double ans = dfs(0, 0, 0, 0, 4, 4);
if (ans > INF / 2) printf("Case %d: -1\n", t);
else printf("Case %d: %.10f\n", t, ans);
}
int main()
{
scanf("%d", &T);
for (int i = 1; i <= T; ++i) solve(i);
}