Acwing218. 扑克牌【期望】

假如现在的牌有n张，已经用去了a，b,c,d张，还没拿到大小王
当前到目标状态要拿取牌数的期望为：
6中情况的期望相加：
拿到a的概率就是(13-a)/n * 期望1
拿到b的概率就是(13-b)/n * 期望2
拿到c的概率就是(13-c)/n * 期望4
拿到d的概率就是(13-d)/n * 期望4
拿到小王的概率就是1/n * 期望5
拿到大王的概率就是1/n * 期望6

因为期望5，6是可以将大小王变成想要的花色，是主观的，所以直接取使得期望更小的那个

#include <stdio.h>
#include <cstring>
#include <algorithm>
#include <vector>
#include <stack>
#include <queue>
#include <iostream>
#include <map>

#define go(i, l, r) for(int i = (l), i##end = (int)(r); i <= i##end; ++i)
#define god(i, r, l) for(int i = (r), i##end = (int)(l); i >= i##end; --i)
#define ios ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define debug_in  freopen("in.txt","r",stdin)
#define debug_out freopen("out.txt","w",stdout);
#define pb push_back
#define all(x) x.begin(),x.end()
#define fs first
#define sc second
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<ll,ll> pii;
const ll maxn = 1e5+10;
const ll maxM = 1e6+10;
const ll inf_int = 1e8;
const ll inf_ll = 1e17;

template<class T>void read(T &x){
    T s=0,w=1;
    char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
    while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
    x = s*w;
}
template<class H, class... T> void read(H& h, T&... t) {
    read(h);
    read(t...);
}

void pt(){ cout<<'\n';}
template<class H, class ... T> void pt(H h,T... t){ cout<<" "<<h; pt(t...);}

//--------------------------------------------
double eps = 1e-7;
int A,B,C,D;
double rec[16][16][16][16][5][5];
double dfs(int a,int b,int c,int d,int x,int y){
    if(rec[a][b][c][d][x][y] > eps) return rec[a][b][c][d][x][y];
    if((a + (x == 1) + (y == 1)) >= A && (b + (x == 2) + (y == 2)) >=B && (c + (x == 3) + (y == 3))>=C && (d + (x == 4) + (y == 4))>=D)
        return 0;
    double left = 54 - a - b - c - d - (x!=0) - (y!=0);
    if(left <= 0) return 0;
    double ans = 0;
    if(a<13) ans += (13-a)/left * dfs(a+1,b,c,d,x,y);
    if(b<13) ans += (13-b)/left * dfs(a,b+1,c,d,x,y);
    if(c<13) ans += (13-c)/left * dfs(a,b,c+1,d,x,y);
    if(d<13) ans += (13-d)/left * dfs(a,b,c,d+1,x,y);
    if(x == 0){
        double cur = 1e18;
        cur = min(cur,1.0/left * dfs(a,b,c,d,1,y));
        cur = min(cur,1.0/left * dfs(a,b,c,d,2,y));
        cur = min(cur,1.0/left * dfs(a,b,c,d,3,y));
        cur = min(cur,1.0/left * dfs(a,b,c,d,4,y));
        ans += cur;
    }
    if(y == 0){
        double cur = 1e18;
        cur = min(cur,1.0/left * dfs(a,b,c,d,x,1));
        cur = min(cur,1.0/left * dfs(a,b,c,d,x,2));
        cur = min(cur,1.0/left * dfs(a,b,c,d,x,3));
        cur = min(cur,1.0/left * dfs(a,b,c,d,x,4));
        ans += cur;
    }
    return rec[a][b][c][d][x][y] = ans + 1;
}
int main() {
//    debug_in;
//    debug_out;

    read(A,B,C,D);
    int more = max(0,(A-13)) + max(0,(B-13)) + max(0,(C-13)) + max(0,(D-13));
    if(more > 2) puts("-1.000");
    else{
        double ans = dfs(0,0,0,0,0,0);
        printf("%.3f\n",ans);
    }

    return 0;
}