UVa 1637 Double Patience (概率DP)

发表于 更新于 分类于

题目

题目大意

36张牌分成9堆, 每堆4张牌。每次可以拿走某两堆顶部的牌, 但需要点数相同。如果有多种拿法则等概率的随机拿。例如, 9堆顶部的牌分别为KS, KH, KD, 9H, 8S, 7C, 7D, 6H, 则有5种拿法(KS, KH), (KS, KD), (KH, KD), (8S, 8D), (7C, 7D), 每种拿法的概率均为15。如果最后拿完所有牌则游戏成功。按顺序给出每堆牌的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];
}