218. 扑克牌 - 记忆化概率dp

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

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

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

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

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

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

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

输入格式

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

输出格式

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

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

数据范围

0≤A,B,C,D≤15

输入样例：

1 2 3 4

输出样例：

16.393

#include
#define IOS ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define endl '\n'
 
using namespace std;
 
typedef pair<int, int> PII;
typedef long long ll;
 
const int N = 15, INF = 1e9;
 
int A, B, C, D;
double f[N][N][N][N][5][5];
 
double dp(int a, int b, int c, int d, int x, int y)
{
    //if(a > 13 || b > 13 || c > 13 || d > 13)return INF;
    
	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)return v = 0;
	
	int sum = a + b + c + d + (x != 4) + (y != 4);
	sum = 54 - sum;
	if(sum == 0)return v = INF;
	
	v = 1;
	if(a < 13)v += (13.0 - a) / sum * dp(a + 1, b, c, d, x, y);
	if(b < 13)v += (13.0 - b) / sum * dp(a, b + 1, c, d, x, y);
	if(c < 13)v += (13.0 - c) / sum * dp(a, b, c + 1, d, x, y);
	if(d < 13)v += (13.0 - d) / sum * dp(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 * dp(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 * dp(a, b, c, d, x, i));
		}
		v += t;
	}
	return v;
}
 
int main()
{
	//IOS
	cin >> A >> B >> C >> D;
	
	memset(f, -1, sizeof f);
	double t = dp(0, 0, 0, 0, 4, 4);
	if(t > INF / 2)t = -1;
	
	printf("%.3lf", t);
	
	return 0;
}

 思路和绿豆蛙那题有点像，一个点的期望等于所有  下一个点的期望乘以相应概率  之和，和图沾点边。

f[a][b][c][d][x][y]

a、b、c、d分别表示每个花色对应的数量，x表示大王，0～3对应所在花色，4表示在牌堆里

小王同理。

正常来说应该是从0 0 0 0 4 4这个状态正着推出答案，但由于终点个数过于多了，难以计算，不如反向建边，以0 0 0 0 4 4为终点。