题目
题目大意
\(36\)张牌分成\(9\)堆, 每堆\(4\)张牌。每次可以拿走某两堆顶部的牌,
但需要点数相同。如果有多种拿法则等概率的随机拿。例如, \(9\)堆顶部的牌分别为KS,
KH, KD, 9H, 8S,
7C, 7D, 6H, 则有\(5\)种拿法(KS,
KH), (KS, KD), (KH,
KD), (8S, 8D), (7C,
7D), 每种拿法的概率均为\(\frac{1}{5}\)。如果最后拿完所有牌则游戏成功。按顺序给出每堆牌的\(4\)张牌, 求成功概率。
题解
记忆化搜索每一种情况,
使用一个std::map<std::vector<int> >记录情况。
代码
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
| #include <map>
#include <cstdio>
#include <vector>
std::map<std::vector<int>, double> hash_table;
char card[9][4][7];
inline double DepthFirstSearch(register std::vector<int>&, const int&);
int main(int argc, char const *argv[]) {
while (~scanf("%s", card[0][0])) {
for (register int c(1); c < 4; ++c) scanf("%s", card[0][c]);
for (register int r(1); r < 9; ++r) {
for (register int c(0); c < 4; ++c) {
scanf("%s", card[r][c]);
}
}
hash_table.clear();
register std::vector<int> status(9, 4);
printf("%.6lf\n", DepthFirstSearch(status, 36));
}
}
inline double DepthFirstSearch(register std::vector<int> &status, const int &c) {
if (!c) return 1.0;
if (hash_table.count(status)) return hash_table[status];
register int total(0);
register double sum(0);
for (register int t(0); t < 9; ++t) if(status[t] > 0){
for (register int i(t + 1); i < 9; ++i) if (status[i] > 0) {
if (card[t][status[t] - 1][0] != card[i][status[i] - 1][0]) continue;
++total,
--status[t],
--status[i],
sum += DepthFirstSearch(status, c - 2),
++status[t],
++status[i];
}
}
hash_table[status] = total ? sum / double(total) : 0.0;
return hash_table[status];
}
|