UVa 12369 Cards

题目概述

Taha\texttt{Taha}Taha有一副特殊的扑克牌，包含525252张常规牌和222张Joker\texttt{Joker}Joker牌。常规牌的花色分为梅花、方块、红心和黑桃四种，每种花色131313张。Joker\texttt{Joker}Joker牌没有花色。Sara\texttt{Sara}Sara随机洗牌后逐张发牌，目标是使得桌面上至少有CCC张梅花、DDD张方块、HHH张红心、SSS张黑桃。当出现Joker\texttt{Joker}Joker时，Taha\texttt{Taha}Taha必须立即将其指定为某种花色，以最小化达成目标所需牌数的期望值。两个Joker\texttt{Joker}Joker的指定可以不同。求这个最小期望值，若不可能达成目标则输出−1.000-1.000−1.000。

输入格式

• 第一行：测试用例数TTT（T<50T < 50T<50）。
• 每行四个整数C,D,H,SC, D, H, SC,D,H,S（0≤C,D,H,S≤150 \le C, D, H, S \le 150≤C,D,H,S≤15）。

输出格式

• 每个测试用例输出一行：Case i: X.XXX，其中X.XXXX.XXXX.XXX为期望值，保留三位小数。

解题思路详解

1. 问题分析

这是一个带有控制的随机过程问题，可以看作一个马尔可夫决策过程（MDP\texttt{MDP}MDP）：

• 状态：已经抽到的四种花色的数量，以及已经使用且分配到各花色的Joker\texttt{Joker}Joker数量。
• 动作：当抽到Joker\texttt{Joker}Joker时，选择将其分配给哪种花色。
• 目标：最小化达到目标所需的期望抽牌数。

2. 状态定义

令(c,d,h,s)(c, d, h, s)(c,d,h,s)表示已经抽到的四种花色的实际牌数（不包括Joker\texttt{Joker}Joker转换来的）。
令(jc,jd,jh,js)(j_c, j_d, j_h, j_s)(jc​,jd​,jh​,js​)表示Joker\texttt{Joker}Joker被指定为四种花色的数量。
由于只有222张 Joker，有0≤jc+jd+jh+js≤20 \le j_c + j_d + j_h + j_s \le 20≤jc​+jd​+jh​+js​≤2。

当前有效牌数为：

• 梅花：c+jcc + j_cc+jc​
• 方块：d+jdd + j_dd+jd​
• 红心：h+jhh + j_hh+jh​
• 黑桃：s+jss + j_ss+js​

终止条件：
c+jc≥C,d+jd≥D,h+jh≥H,s+js≥S c + j_c \ge C,\quad d + j_d \ge D,\quad h + j_h \ge H,\quad s + j_s \ge Sc+jc​≥C,d+jd​≥D,h+jh​≥H,s+js​≥S

3. 状态转移与期望计算

设E(c,d,h,s,jc,jd,jh,js)E(c, d, h, s, j_c, j_d, j_h, j_s)E(c,d,h,s,jc​,jd​,jh​,js​)为当前状态下的最小期望抽牌数（从当前开始到结束）。
当前已抽牌数：
drawn=c+d+h+s+jc+jd+jh+js \texttt{drawn} = c + d + h + s + j_c + j_d + j_h + j_sdrawn=c+d+h+s+jc​+jd​+jh​+js​
剩余牌数：
remain=54−drawn \texttt{remain} = 54 - \texttt{drawn}remain=54−drawn

若remain=0\texttt{remain} = 0remain=0且未达标，则E=∞E = \inftyE=∞（不可达）。

对于下一张牌，可能是：

• 梅花：概率pc=13−cremainp_c = \frac{13 - c}{\text{remain}}pc​=remain13−c​，期望贡献pc×(1+E(c+1,d,h,s,jc,jd,jh,js))p_c \times (1 + E(c+1, d, h, s, j_c, j_d, j_h, j_s))pc​×(1+E(c+1,d,h,s,jc​,jd​,jh​,js​))
• 方块：概率pd=13−dremainp_d = \frac{13 - d}{\text{remain}}pd​=remain13−d​，期望贡献pd×(1+E(c,d+1,h,s,jc,jd,jh,js))p_d \times (1 + E(c, d+1, h, s, j_c, j_d, j_h, j_s))pd​×(1+E(c,d+1,h,s,jc​,jd​,jh​,js​))
• 红心：概率ph=13−hremainp_h = \frac{13 - h}{\text{remain}}ph​=remain13−h​，期望贡献ph×(1+E(c,d,h+1,s,jc,jd,jh,js))p_h \times (1 + E(c, d, h+1, s, j_c, j_d, j_h, j_s))ph​×(1+E(c,d,h+1,s,jc​,jd​,jh​,js​))
• 黑桃：概率ps=13−sremainp_s = \frac{13 - s}{\text{remain}}ps​=remain13−s​，期望贡献ps×(1+E(c,d,h,s+1,jc,jd,jh,js))p_s \times (1 + E(c, d, h, s+1, j_c, j_d, j_h, j_s))ps​×(1+E(c,d,h,s+1,jc​,jd​,jh​,js​))
• Joker\texttt{Joker}Joker：概率pj=2−(jc+jd+jh+js)remainp_j = \frac{2 - (j_c + j_d + j_h + j_s)}{\text{remain}}pj​=remain2−(jc​+jd​+jh​+js​)​，此时需要选择一种花色使得后续期望最小：
  min⁡{1+E(c,d,h,s,jc+1,jd,jh,js)1+E(c,d,h,s,jc,jd+1,jh,js)1+E(c,d,h,s,jc,jd,jh+1,js)1+E(c,d,h,s,jc,jd,jh,js+1) \min \begin{cases} 1 + E(c, d, h, s, j_c+1, j_d, j_h, j_s) \\ 1 + E(c, d, h, s, j_c, j_d+1, j_h, j_s) \\ 1 + E(c, d, h, s, j_c, j_d, j_h+1, j_s) \\ 1 + E(c, d, h, s, j_c, j_d, j_h, j_s+1) \end{cases}min⎩⎨⎧​1+E(c,d,h,s,jc​+1,jd​,jh​,js​)1+E(c,d,h,s,jc​,jd​+1,jh​,js​)1+E(c,d,h,s,jc​,jd​,jh​+1,js​)1+E(c,d,h,s,jc​,jd​,jh​,js​+1)​

总期望：
E=∑suitpsuit×(1+Enext)+pj×Ejoker-best E = \sum_{\texttt{suit}} p_{\texttt{suit}} \times (1 + E_{\texttt{next}}) + p_j \times E_{\texttt{joker-best}}E=suit∑​psuit​×(1+Enext​)+pj​×Ejoker-best​

4. 可行性判断

由于每种花色最多131313张牌，若目标超过131313，则超出的部分必须由Joker\texttt{Joker}Joker补充。
设：
needExtra=max⁡(0,C−13)+max⁡(0,D−13)+max⁡(0,H−13)+max⁡(0,S−13) \texttt{needExtra} = \max(0, C-13) + \max(0, D-13) + \max(0, H-13) + \max(0, S-13)needExtra=max(0,C−13)+max(0,D−13)+max(0,H−13)+max(0,S−13)
若needExtra>2\texttt{needExtra} > 2needExtra>2，则即使全部Joker\texttt{Joker}Joker都用上也不够，输出−1.000-1.000−1.000。

5. 算法设计

使用记忆化搜索（Memoization\texttt{Memoization}Memoization）实现动态规划：

• 状态维数：14×14×14×14×3×3×3×3≈3.8×10614 \times 14 \times 14 \times 14 \times 3 \times 3 \times 3 \times 3 \approx 3.8 \times 10^614×14×14×14×3×3×3×3≈3.8×106，可以存储。
• 递归边界：达标时返回000，无牌可抽时返回∞\infty∞。
• 利用概率计算期望，对Joker\texttt{Joker}Joker决策取最小值。

6. 复杂度分析

• 状态数：144×34≈3.8×10614^4 \times 3^4 \approx 3.8 \times 10^6144×34≈3.8×106
• 每个状态转移：常数时间（最多888种可能）
• 总时间复杂度：O(状态数×8)O(\text{状态数} \times 8)O(状态数×8)，在可接受范围内。

代码实现

// Cards// UVa ID: 12369// Verdict: Accepted// Submission Date: 2025-12-15// UVa Run Time: 1.010s//// 版权所有（C）2025，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;constdoubleINF=1e30;// 表示无穷大，用于不可达状态constintMAXN=14;doublememo[MAXN][MAXN][MAXN][MAXN][3][3][3][3];boolvisited[MAXN][MAXN][MAXN][MAXN][3][3][3][3];intneedC,needD,needH,needS;doubledfs(intc,intd,inth,ints,intjc,intjd,intjh,intjs){// jc, jd, jh, js 分别表示Joker被指定为梅花、方块、红心、黑桃的数量// 总Joker使用数 = jc + jd + jh + js ≤ 2inttotalC=c+jc;inttotalD=d+jd;inttotalH=h+jh;inttotalS=s+js;if(totalC>=needC&&totalD>=needD&&totalH>=needH&&totalS>=needS){return0.0;// 目标已达成，无需再抽牌}// 边界检查if(c>13||d>13||h>13||s>13)returnINF;if(jc+jd+jh+js>2)returnINF;if(c+d+h+s+jc+jd+jh+js>54)returnINF;intstateC=min(c,13);intstateD=min(d,13);intstateH=min(h,13);intstateS=min(s,13);if(visited[stateC][stateD][stateH][stateS][jc][jd][jh][js]){returnmemo[stateC][stateD][stateH][stateS][jc][jd][jh][js];}intremainingClubs=13-c;intremainingDiamonds=13-d;intremainingHearts=13-h;intremainingSpades=13-s;intremainingJokers=2-(jc+jd+jh+js);intdrawnCards=c+d+h+s+jc+jd+jh+js;intremainingCards=54-drawnCards;if(remainingCards==0){// 无牌可抽仍未达标visited[stateC][stateD][stateH][stateS][jc][jd][jh][js]=true;memo[stateC][stateD][stateH][stateS][jc][jd][jh][js]=INF;returnINF;}doubleexpected=0.0;// 抽到梅花的期望if(remainingClubs>0){doubleprob=(double)remainingClubs/remainingCards;expected+=prob*(1.0+dfs(c+1,d,h,s,jc,jd,jh,js));}// 抽到方块的期望if(remainingDiamonds>0){doubleprob=(double)remainingDiamonds/remainingCards;expected+=prob*(1.0+dfs(c,d+1,h,s,jc,jd,jh,js));}// 抽到红心的期望if(remainingHearts>0){doubleprob=(double)remainingHearts/remainingCards;expected+=prob*(1.0+dfs(c,d,h+1,s,jc,jd,jh,js));}// 抽到黑桃的期望if(remainingSpades>0){doubleprob=(double)remainingSpades/remainingCards;expected+=prob*(1.0+dfs(c,d,h,s+1,jc,jd,jh,js));}// 抽到Joker的期望if(remainingJokers>0){doubleprob=(double)remainingJokers/remainingCards;doublebest=INF;// 尝试四种花色，选择期望最小的if(jc+jd+jh+js<2){best=min(best,1.0+dfs(c,d,h,s,jc+1,jd,jh,js));best=min(best,1.0+dfs(c,d,h,s,jc,jd+1,jh,js));best=min(best,1.0+dfs(c,d,h,s,jc,jd,jh+1,js));best=min(best,1.0+dfs(c,d,h,s,jc,jd,jh,js+1));}expected+=prob*best;}visited[stateC][stateD][stateH][stateS][jc][jd][jh][js]=true;memo[stateC][stateD][stateH][stateS][jc][jd][jh][js]=expected;returnexpected;}intmain(){intT;cin>>T;for(intt=1;t<=T;t++){cin>>needC>>needD>>needH>>needS;// 检查是否可能intrequired=0;if(needC>13)required+=needC-13;if(needD>13)required+=needD-13;if(needH>13)required+=needH-13;if(needS>13)required+=needS-13;if(required>2){printf("Case %d: -1.000\n",t);continue;}// 初始化记忆化数组memset(visited,0,sizeof(visited));doubleresult=dfs(0,0,0,0,0,0,0,0);if(result>1e20){printf("Case %d: -1.000\n",t);}else{printf("Case %d: %.3lf\n",t,result);}}return0;}

总结

本题的核心在于状态的定义和期望的计算：

• 状态需要区分“抽到的花色牌”和“Joker\texttt{Joker}Joker转换的花色牌”，因为Joker\texttt{Joker}Joker的分配是可控决策。
• 期望计算采用标准的条件期望公式，对Joker\texttt{Joker}Joker的决策取最小值。
• 使用记忆化搜索避免重复计算，确保在合理时间内完成。