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), 每种拿法的概率均为\(\frac{1}{5}\)。如果最后拿完所有牌则游戏成功。按顺序给出每堆牌的\(4\)张牌, 求成功概率。

题解

记忆化搜索每一种情况, 使用一个std::map<std::vector<int> >记录情况。

代码

#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];
}