POJ2794 Double Patience[离散概率状压DP]-白红宇

POJ2794 Double Patience[离散概率状压DP]

阅读量：794 次

发布时间：2023-03-03

本文共 1924 字，大约阅读时间需要 6 分钟。

为了计算George在Double Patience游戏中随机策略下赢的概率，我们可以采用动态规划和记忆化搜索的方法。以下是详细的解决方案：

方法思路

状态表示：将每个堆的状态表示为五进制数，其中每一位表示该堆剩余卡片的位置（0到4）。

动态规划：使用动态规划数组d，其中d[u]表示从状态u出发George赢的概率。

状态转换：对于每个状态，检查所有可能的两堆配对，计算配对后的新状态，并递归计算新状态的赢概率。

记忆化技术：使用一个数组存储已经计算过的状态结果，避免重复计算。

初始状态：初始状态为所有九堆都有四张卡片，对应的五进制数为999999（即1953124）。

解决代码

#include 
   
    #include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;const int N = 1953125;const string suits = "SCDHH";const string ranks = "A23456789TJQK";int c[10][5] = {}; // c[i][j] 表示第i堆在第j层的卡的花色int s[5] = {};    // s[i] 表示第i堆的卡的顺序int M = 1953124;  // 初始状态vector
        
          a(10); // 用于转换状态到五进制数int compute_state(int u) { for (int i = 1; i <= 9; ++i) { a[i] = 0; } for (int i = 9; i >= 1; --i) { int t = u / (int)pow(5, 9 - i); a[i] = t % 5; u /= (int)pow(5, 9 - i); } return a;}double dp(int u) { static vector
         
           d(N, -1); if (d[u] != -1) return d[u]; d[u] = 1.0; vector
          
           
            > pairs; for (int i = 1; i <= 9; ++i) { for (int j = i + 1; j <= 9; ++j) { if (c[i][a[i]] == c[j][a[j]]) { pairs.emplace_back(i, j); } } } if (pairs.empty()) { d[u] = 0.0; return d[u]; } int cnt = pairs.size(); for (auto& p : pairs) { int i = p.first; int j = p.second; int t = 0; for (int k = 9; k >= 1; --k) { t = t * 5; if (k == i || k == j) { t += a[k] - 1; } else { t += a[k]; } } t /= 5; d[u] += dp(t); } if (cnt) { d[u] /= cnt; } else { d[u] = 0.0; } return d[u];}int main() { for (int i = 1; i <= 9; ++i) { for (int j = 1; j <= 4; ++j) { string card; card += s[i]; card += c[i][j]; c[i][j] = card[1]; } } d[M] = 1.0; cout << fixed << setprecision(6) << dp(M); return 0;}