带限制的期望我们一般喜欢用 DP 来解决，因为这样能够更好的处理相邻之间的限制。其实一般说来好多期望都是通过 DP 来解决，而一小部分是直接能够算出概率求得。

观察题目总共44 个限制，同时还有大小王的灵活使用。不难有状态f(a,b,c,d,e,f)f(a,b,c,d,e,f)，表示用了aa 个黑桃，bb 个红桃，cc 个梅花，dd 个方块，小王状态ee，大王状态ff。其中大小王状态格式为：00 为未使用，1→31\rightarrow 3 为当作黑桃，红桃，梅花，方块。

不妨设已经用过的牌数量为sumsum，显然sum=a+b+c+d+[e≠0]+[f≠0]sum=a+b+c+d+[e\neq 0]+[f \neq 0]。对于一个状态合法，即满足a,b,c,d≤13,sum≤54a,b,c,d\le 13,sum \le 54。考虑转移方程，有如下情况：

  • 黑桃：抽中的概率为13−a54−sum\dfrac{13-a}{54-sum}，那么期望即为13−a54−sum+f(a+1,b,c,d,e,f)\dfrac{13-a}{54-sum}+f(a+1,b,c,d,e,f)。
  • 红桃：抽中的概率为13−b54−sum\dfrac{13-b}{54-sum}，那么期望即为13−b54−sum+f(a,b+1,c,d,e,f)\dfrac{13-b}{54-sum}+f(a,b+1,c,d,e,f)。
  • 梅花：抽中的概率为13−c54−sum\dfrac{13-c}{54-sum}，那么期望即为13−c54−sum+f(a,b,c+1,d,e,f)\dfrac{13-c}{54-sum}+f(a,b,c+1,d,e,f)。
  • 方块：抽中的概率为13−d54−sum\dfrac{13-d}{54-sum}，那么期望即为13−d54−sum+f(a,b,c,d+1,e,f)\dfrac{13-d}{54-sum}+f(a,b,c,d+1,e,f)。
  • 小王：这里有点不同，能抽中小王当且仅当[e=0][e=0] 成立，那么成立时概率即为154−sum\dfrac{1}{54-sum}，考虑如何转移，题面中已经说明会选择期望最小的的来转移，那么期望即为154−sum×min⁡i=11≤i≤4f(a,b,c,d,i,f)\dfrac{1}{54-sum}\times \min_{i=1}^{1\le i \le 4} f(a,b,c,d,i,f)。
  • 大王：同上推导，当且仅当[f=0][f=0] 成立，即154−sum×min⁡i=11≤i≤4f(a,b,c,d,e,i)\dfrac{1}{54-sum}\times \min_{i=1}^{1\le i \le 4} f(a,b,c,d,e,i)。

最后加起来即可。我们转移的顺序一般从终止状态开始计算，而起始作为目标，因为在很多情况下，终止状态有很多，而起始是唯一的。所以一般期望 DP 我们会采取倒推的手段，区别于概率 DP 的正推。

注意到状态转移太过于难受，我们考虑记忆化搜索的方式实现，这样起码好些不坐牢，故代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
#include<bits/stdc++.h>
using namespace std;
constexpr int MN=25;
constexpr double INF=1e18;
int A,B,C,D;
bool vis[MN][MN][MN][MN][5][5];
double dp[MN][MN][MN][MN][5][5];

double dfs(int a,int b,int c,int d,int e,int f){
    if(vis[a][b][c][d][e][f]) return dp[a][b][c][d][e][f];
    vis[a][b][c][d][e][f]=1;
    int sum=a+b+c+d+(e!=0)+(f!=0);
    double val=0;
    if(a>13||b>13||c>13||d>13||sum>54){
        dp[a][b][c][d][e][f]=INF;
        return dp[a][b][c][d][e][f];
    }
    if(a+(e==1)+(f==1)>=A&&b+(e==2)+(f==2)>=B&&c+(e==3)+(f==3)>=C&&d+(e==4)+(f==4)>=D) dp[a][b][c][d][e][f]=0;
    else{
        val+=(13.0-a)/(54.0-sum)*dfs(a+1,b,c,d,e,f);
        val+=(13.0-b)/(54.0-sum)*dfs(a,b+1,c,d,e,f);
        val+=(13.0-c)/(54.0-sum)*dfs(a,b,c+1,d,e,f);
        val+=(13.0-d)/(54.0-sum)*dfs(a,b,c,d+1,e,f);
        if(e==0){
            double minn=INF;
            for(int i=1;i<=4;i++) minn=min(minn,dfs(a,b,c,d,i,f));
            val+=1.0/(54.0-sum)*minn;
        }
        if(f==0){
            double minn=INF;
            for(int i=1;i<=4;i++) minn=min(minn,dfs(a,b,c,d,e,i));
            val+=1.0/(54.0-sum)*minn;
        }
        dp[a][b][c][d][e][f]=val+1.0;
    }
    return dp[a][b][c][d][e][f];
}

void solve(){
    cin>>A>>B>>C>>D;
    memset(dp,0,sizeof(dp));
    memset(vis,0,sizeof(vis));
    dfs(0,0,0,0,0,0);
    if(dp[0][0][0][0][0][0]>54) cout<<"-1.000\n";
    else cout<<fixed<<setprecision(3)<<dp[0][0][0][0][0][0]<<'\n';
}

int main(){
    int T,cnt=0;
    cin>>T;
    while(T--){
        cout<<"Case "<<++cnt<<": ";
        solve();
    }
    return 0;
}