题意：
一副牌， 每个花色13张牌，加上大小王，共54张。
遇到大小王可以代替其中某种花色。
给定C, D, H, S。
每次抽一张牌， 问抽到C张梅花， D张方块， H张红桃， S张黑桃所需要的最小次数的期望。
思路：
用dp[c][d][h][s][staues]表示当前有c张梅花，d张方块，h张红桃，s张黑桃，大小王的状态为staues时， 达到目标所需要的期望。
staues 用余三法进行状压， 因为大小王有两张， 变成某种花色的牌的数目就可能是0,1,2。
四种花色， 也就是2 * 1 + 2 * 3 + 2 * 9 + 2 * 27 = 80种状态。
再分情况考虑， 用dfs进行求解。
代码：
1 #include <cmath> 2 #include <cstdio> 3 #include <cstring> 4 #include <cstdlib> 5 #include <ctime> 6 #include <set> 7 #include <map> 8 #include <list> 9 #include <queue> 10 #include <string> 11 #include <vector> 12 #include <fstream> 13 #include <iterator> 14 #include <iostream> 15 #include <algorithm> 16 using namespace std; 17 #define LL long long 18 #define INF 0x3f3f3f3f 19 #define MOD 1000000007 20 #define eps 1e-6 21 #define MAXN 16 22 #define MAXM 82 23 #define dd cout<<"debug"<<endl 24 #define p(x) printf("%d ", x) 25 #define pd(x) printf("%.7lf ", x) 26 #define k(x) printf("Case %d: ", ++x) 27 #define s(x) scanf("%d", &x) 28 #define sd(x) scanf("%lf", &x) 29 #define mes(x, d) memset(x, d, sizeof(x)) 30 #define do(i, x) for(i = 0; i < x; i ++) 31 int C, D, H, S; 32 double dp[MAXN][MAXN][MAXN][MAXN][MAXM]; 33 void init() 34 { 35 int i, j, k, m, l; 36 do(i, MAXN) 37 do(j, MAXN) 38 do(k, MAXN) 39 do(m, MAXN) 40 do(l, MAXM) 41 dp[i][j][k][m][l] = -1.0; 42 } 43 bool is_ok(int c, int d, int h, int s, int j) 44 { 45 int bit[4] = {0, 0, 0, 0}; 46 int cnt = 0; 47 while(j) 48 { 49 bit[cnt ++] = j % 3; 50 j /= 3; 51 } 52 c += bit[0]; 53 d += bit[1]; 54 h += bit[2]; 55 s += bit[3]; 56 if(c >= C && d >= D && h >= H && s >= S) 57 return true; 58 return false; 59 } 60 double dfs(int c, int d, int h, int s, int j) 61 { 62 double &res = dp[c][d][h][s][j]; 63 if(res != -1.0) 64 return res; 65 if(is_ok(c, d, h, s, j)) 66 return res = 0.0; 67 res = 0.0; 68 int bit[4] = {0, 0, 0, 0}; 69 int num = 0; 70 int jj = j; 71 for(int i = 0; i < 4; i ++) 72 { 73 bit[i] = j % 3; 74 j /= 3; 75 num += bit[i]; 76 } 77 int sum = 54 - (c + d + h + s + num); 78 if(c < 13 && sum) 79 { 80 double p = (13 - c) * 1.0 / sum; 81 res += (dfs(c + 1, d, h, s, jj) + 1) * p; 82 } 83 if(d < 13 && sum) 84 { 85 double p = (13 - d) * 1.0 / sum; 86 res += (dfs(c, d + 1, h, s, jj) + 1) * p; 87 } 88 if(h < 13 && sum) 89 { 90 double p = (13 - h) * 1.0 / sum; 91 res += (dfs(c, d, h + 1, s, jj) + 1) * p; 92 } 93 if(s < 13 && sum) 94 { 95 double p = (13 - s) * 1.0 / sum; 96 res += (dfs(c, d, h, s + 1, jj) + 1) * p; 97 } 98 if(num < 2 && sum) 99 { 100 double p = (2 - num) * 1.0 / sum; 101 int cnt = bit[0] + 1 + bit[1] * 3 + bit[2] * 9 + bit[3] * 27; 102 double temp = dfs(c, d, h, s, cnt); 103 104 cnt = bit[0] + (bit[1] + 1) * 3 + bit[2] * 9 + bit[3] * 27; 105 temp = min(temp, dfs(c, d, h, s, cnt)); 106 107 cnt = bit[0] + bit[1] * 3 + (bit[2] + 1) * 9 + bit[3] * 27; 108 temp = min(temp, dfs(c, d, h, s, cnt)); 109 110 cnt = bit[0] + bit[1] * 3 + bit[2] * 9 + (bit[3] + 1) * 27; 111 temp = min(temp, dfs(c, d, h, s, cnt)); 112 113 res += (temp + 1.0) * p; 114 } 115 return res; 116 } 117 118 int main() 119 { 120 int T; 121 int kcase = 0; 122 scanf("%d", &T); 123 while(T --) 124 { 125 scanf("%d %d %d %d", &C, &D, &H, &S); 126 int x = 0; 127 init(); 128 x = (C > 13? C - 13 : 0) + (D > 13? D - 13 : 0) + (H > 13? H - 13 : 0) + (S > 13? S - 13 : 0); 129 if(x > 2) 130 printf("Case %d: -1 ", ++ kcase); 131 else 132 { 133 double ans = dfs(0, 0, 0, 0, 0); 134 printf("Case %d: %.7lf ", ++ kcase, ans); 135 } 136 } 137 return 0; 138 }