AcWing 218. 扑克牌

题目传送门

一、题意分析

我们使用\(F(a, b, c, d, x, y)\)表示现在已经翻出\(a\)张黑桃，\(b\)张红桃，\(c\)张梅花，\(d\)张方块，且大小王的状态为\(x\)、\(y\)。以小王为例,当\(x=4\)时,表示小王还没翻出来,\(x≠4时\),\(x\)取\(0,1,2,3\),分别表示小王放入了四个花色的牌堆中,\(0\):黑桃、\(1\):红桃、\(2\):梅花、\(3\):方块。

我们把问题转化成有向无环图,每个节点表示一个状态,边权是\(1\),表示翻出的牌数加\(1\)

起点:\(F[0, 0, 0, 0, 4, 4]\)

终点:
\(\displaystyle a + (x == 0) + (y == 0)\geqslant A \\ b + (x == 1) + (y == 1) \geqslant B \\ c + (x == 2)+(y == 2) \geqslant C \\ d + (x == 3) + (y == 3) \geqslant D\)
从起点到终点的期望路径。

由假设当前的节点是\(x\),出边指向\(y_1, y_2, ...y_k\). 走向不同的出边的概率分别是\(p_1,p_2,... p_k\).

那么节点\(x\)的期望值是:$$\LARGE F[x] = \sum_{i=1}^{k}p[i] * (F[y_i] + 1)$$

接下来我们求\(p[i]\),假设我们当前已经抽取了\(sum\)张牌:

\[\large sum=a+b+c+d+(x≠4)+(y≠4) \]

还剩下\(54-sum\)张牌,其中有\(13-a\)张黑桃.故翻开一张黑桃的概率为\((13 - a) / (54 - sum)\), 状态转移为\(F(a + 1, b, c, d, x, y)\).其余\(3\)个花色同理.

特别地,当\(x=4\)时,有\(1/(54-sum)\)的概率抽到小王,根据题意,小王变成某个花色后,期望值要尽可能的小,即

\[\large \min_{0<=x'<=3}(F[a,b,c,d,x',y])$$,大王同理. 综上所述,状态的转移为 $$\large F[a,b,c,d,x,y]=1+\frac{13-a}{54-sum}\times F[a+1,b,c,d,x,y] \\ +\frac{13-b}{54-sum}\times F[a,b+1,c,d,x,y] \\ +\frac{13-c}{54-sum}\times F[a,b,c+1,d,x,y] \\ +\frac{13-d}{54-sum}\times F[a,b,c,d+1,x,y] \\ +\frac{1}{54-sum}\times \min_{0<=x'<=3}(F[a,b,c,d,x',y]) \\ +\frac{1}{54-sum}\times \min_{0<=y'<=3}(F[a,b,c,d,x,y']) \]

二、实现代码

#include 

using namespace std;

const int N = 14;           //每个花色共13张牌
const double INF = 1e20;    //在 double情况下的极大值，yxc用了1e20
int A, B, C, D;             //四个花色需要达到的个数
double f[N][N][N][N][5][5]; //黑红花片+小王+大王

//找出递推关系式，递推=dp
double dp(int a, int b, int c, int d, int x, int y) {
    //记忆化搜索
    double &v = f[a][b][c][d][x][y];
    if (v >= 0) return v;

    int as = a + (x == 0) + (y == 0); // 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 0; 

    int sum = a + b + c + d + (x != 4) + (y != 4); // 4表示还没有被翻出; x!=4 表示小王已经被翻出，总数需要+1，大王同理
    sum = 54 - sum;                                //剩余牌数量
    if (sum <= 0) return INF;                      //没有牌了，返回正无穷

    v = 1; // 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() {
    cin >> A >> B >> C >> D;
    memset(f, -1, sizeof f); //标识未使用状态，-1代表没算过，0表示算过，结果是0

    double t = dp(0, 0, 0, 0, 4, 4); //结果保存到f(0,0,0,0,4,4)里面，从结果向前倒推

    //这是啥意思？
    if (t > INF / 2) t = -1;

    //结果保留小数点后3位小数
    printf("%.3lf\n", t);
    return 0;
}

三、\(Q\):期望值为什么可以初始化为\(1\)?

这题思路还是逆推

\(f[i]\): 从\(i\)卡牌状态到终点状态所需要的期望卡牌数

每次抽一张牌变到下个状态，所以每条路径的权值为\(1\)

\[\large f[v]=p_1×(f[1]+1)+p_2×(f[2]+1)+p_3×(f[3]+1)+…+p_k×(f[k]+1) = \\ \sum_{i=1}^{k}p_i+\sum_{i=1}^{k}p_i \times f[i] \]

因为\(v\)一定能到达下个局面，所以下个状态的概率和为\(1\)，这里的\(\large \displaystyle \sum_{i=1}^{k}p_i=1\) 那么就有：\(\displaystyle \large f[v]=1+\sum_{i=1}^{k}p_i \times f[i]\) 
综上这里的\(f[v]\)可以初始化为\(1\)！