0x38 概率与数学期望例题3：扑克牌

2018chenyu · 2019-12-14 17:32:19 · 个人记录

Description

Admin生日那天，Rainbow来找Admin玩扑克牌。
玩着玩着Rainbow觉得太没意思了,于是决定给Admin一个考验。
Rainbow把一副扑克牌(54张)随机洗开，倒扣着放成一摞。
然后Admin从上往下依次翻开每张牌，每翻开一张黑桃、红桃、梅花或者方块，就把它放到对应花色的堆里去。
Rainbow想问问Admin，得到A张黑桃、B张红桃、C张梅花、D张方块需要翻开的牌的张数的期望值E是多少？
特殊地，如果翻开的牌是大王或者小王，Admin将会把它作为某种花色的牌放入对应堆中,使得放入之后E的值尽可能小。
由于Admin和Rainbow还在玩扑克，所以这个程序就交给你来写了。

Input

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

Output

输出需要翻开的牌数的期望值E，四舍五入保留3位小数。
如果不可能达到输入的状态，输出-1.000。

Hint

0≤A,B,C,D≤15

Sample Input

1 2 3 4

Sample Output

16.393

Analyse

数学期望+动态规划 的 Dark ♂ 题，做起来有点像“杨老师的照相队列”（但是用不到“杨氏矩阵”之类的鬼畜玩意儿）；

设 dp[a][b][c][d][e][f] 表示当前已经翻开了 a 张黑桃，b 张红桃，c 张梅花，d 张方块，小王状态为 e，大王状态为 f（王的状态：1：黑桃，2：红桃，3：梅花，4：方块）。即已经翻开了 cnt=a+b+c+d+(e\gt0)+(f\gt0) 张牌，还剩下 54-cnt 张牌。

考虑花，以黑桃举例（假设 a\lt13），还剩下 13-a 张黑桃，故多摸一张黑桃的期望值为 dp[a+1][b][c][d][e][f]*(13-a)/cnt ；
考虑王，以小王举例（假设 e=0），根据题意得：应选择使期望值最小的花色，故把小王看作某一种花色的期望值为 \min_{1\lt e'\lt 4}\left\{dp[a][b][c][d][e'][f]\right\} ；

综上所述，有：

&dp[a][b][c][d][e][f]=\\ &dp[a+1][b][c][d][e][f]*(13-a)/cnt+\\ &dp[a][b+1][c][d][e][f]*(13-b)/cnt+\\ &dp[a][b][c+1][d][e][f]*(13-c)/cnt+\\ &dp[a][b][c][d+1][e][f]*(13-d)/cnt+\\ &\min_{1\lt e'\lt 4}\left\{dp[a][b][c][d][e'][f]\right\}+\min_{1\lt f'\lt 4}\left\{dp[a][b][c][d][e][f']\right\} \end{aligned}

那么显而易见地，更新当前状态需要用到子状态，用记忆化搜索可以水过去。有几个需要注意的细节：

如果要用王补位的牌数\gt2，无解；
每一个有意义的 dp[a][b][c][d][e][f] 都要初始化为 1 ，因为本身就摸了一张牌；
对于记忆化搜索里的状态，如果所有牌的状态都已经满足，返回零即可；

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
inline int read()
{
    int x=0;bool f=false;
    char ch=getchar();
    while(ch<'0' || ch>'9') f|=(ch=='-'),ch=getchar();
    while(ch>='0'&&ch<='9') x=x*10+(ch^48),ch=getchar();
    return f?-x:x;
}
int A,B,C,D;
double dp[14][14][14][14][5][5];//四个花色的数量、两个王代表的花色 
bool v[14][14][14][14][5][5];
double dfs(int a,int b,int c,int d,int e,int f)
{
    if(v[a][b][c][d][e][f]) return dp[a][b][c][d][e][f];
    v[a][b][c][d][e][f]=true;
    int aa=a+(e==1)+(f==1),bb=b+(e==2)+(f==2);
    int cc=c+(e==3)+(f==3),dd=d+(e==4)+(f==4);//统计花色实际数量 
    if(aa>=A && bb>=B && cc>=C && dd>=D) return 0;//都满足了还要求什么
    int cnt=54-aa-bb-cc-dd;//还有多少种结果（即等可能性为1/cnt）
    if(cnt<=0) return 1e10;//莫得机会了
    double &ans=dp[a][b][c][d][e][f];ans=1;//本身就摸了一张牌 
    if(a<13) ans+=dfs(a+1,b,c,d,e,f)*(13-a)/cnt;
    if(b<13) ans+=dfs(a,b+1,c,d,e,f)*(13-b)/cnt;
    if(c<13) ans+=dfs(a,b,c+1,d,e,f)*(13-c)/cnt;
    if(d<13) ans+=dfs(a,b,c,d+1,e,f)*(13-d)/cnt;
    if(!e)
    {
        double tmp=dfs(a,b,c,d,1,f);
        tmp=min(tmp,dfs(a,b,c,d,2,f));
        tmp=min(tmp,dfs(a,b,c,d,3,f));
        tmp=min(tmp,dfs(a,b,c,d,4,f));
        ans+=tmp/cnt;
    }
    if(!f)
    {
        double tmp=dfs(a,b,c,d,e,1);
        tmp=min(tmp,dfs(a,b,c,d,e,2));
        tmp=min(tmp,dfs(a,b,c,d,e,3));
        tmp=min(tmp,dfs(a,b,c,d,e,4));
        ans+=tmp/cnt;
    }
    return ans;
}
int main()
{
    A=read();B=read();C=read();D=read();
    if((A>13)*(A-13)+(B>13)*(B-13)+(C>13)*(C-13)+(D>13)*(D-13)>2) return puts("-1.000"),0;//王不够补位 
    printf("%.3lf\n",dfs(0,0,0,0,0,0)>100?-1:dp[0][0][0][0][0][0]);
    return 0;
}

Summary

搞 数学期望值 时，我们通常把终止情况设为初值，把起始情况情况设为目标，倒推以扫出答案。这是因为终止情况是唯一的，其概率一定为1，除以上一步选择终止情况的次数求出期望值，从而解题。

0x38 概率与数学期望 例题3：扑克牌