题解：Double Patience 游戏获胜概率计算（C++ 实现）

问题分析

Double Patience 是一个单人卡牌游戏，玩家需要通过移除等级相同的顶牌对来清空桌面。George 的策略是在所有可能的合法移动中随机选择一个。我们需要计算从初始牌局出发，George 按照此策略获胜的概率。

解题思路

1. 状态表示：使用一个整数 s 来编码当前各堆的顶牌状态。每堆牌的剩余数量用 4 位二进制数表示（因为每堆最多有 4 张牌），因此总状态数为 (5^9 = 1953125)。
2. 递归与记忆化：使用递归函数 DP 计算从当前状态 s 获胜的概率，并用 vis 数组和 dp 数组进行记忆化存储。
3. 状态转移：对于当前状态，枚举所有可能的合法移动（即选择两张等级相同的顶牌），递归计算新状态的获胜概率，并加权平均。
4. 终止条件：
   • 无牌时（状态 0）获胜概率为 1。
   • 有牌但无合法移动时获胜概率为 0。

代码实现

#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

char card[10][5];  // card[i][j] 表示第 i 堆的第 j 张牌的等级
bool vis[2000000]; // 记忆化数组，标记状态是否已计算
double dp[2000000]; // dp[s] 表示状态 s 的获胜概率

// 将状态编码为整数
int code(int *a) {
    static int s;
    s = 0;
    for (int i = 9; i >= 1; i--)
        s = s * 5 + a[i];
    return s;
}

// 解码状态
void decode(int s, int *a) {
    for (int i = 1; i <= 9; i++)
        a[i] = s % 5, s /= 5;
}

// 递归计算获胜概率
double DP(int s) {
    if (vis[s]) return dp[s];
    vis[s] = 1;
    int a[10], cnt = 0;
    decode(s, a); // 解码当前状态

    // 枚举所有可能的合法移动
    for (int i = 1; i <= 9; i++)
        for (int j = i + 1; j <= 9; j++) {
            if (!a[i] || !a[j] || card[i][a[i]] != card[j][a[j]]) continue;
            a[i]--; a[j]--; cnt++; // 移除顶牌
            int _s = code(a);      // 新状态
            dp[s] += DP(_s);       // 累加新状态的获胜概率
            a[i]++; a[j]++;        // 恢复状态
        }

    if (cnt) dp[s] /= cnt; // 加权平均
    return dp[s];
}

int main() {
    static char S[5];
    // 读取输入，初始化牌局
    for (int i = 1; i <= 9; i++)
        for (int j = 1; j <= 4; j++)
            scanf("%s", S), card[i][j] = S[0];

    vis[0] = 1; // 初始状态（无牌）的获胜概率为 1
    dp[0] = 1;
    printf("%.6lf\n", DP(1953124)); // 初始状态（所有牌都在）的获胜概率
    return 0;
}

代码解释

1. 输入处理：读取 9 堆牌，每堆 4 张，存储在 card 数组中。
2. 状态编码与解码：
   • code 函数将当前各堆的顶牌状态编码为一个整数。
   • decode 函数将整数状态解码为各堆的顶牌数量。
3. 递归函数 DP：
   • 如果状态 s 已计算，直接返回 dp[s]。
   • 否则，枚举所有合法移动，递归计算新状态的获胜概率，并加权平均。
4. 主函数：初始化牌局，计算并输出初始状态（所有牌都在）的获胜概率。

注意事项

• 状态编码使用 5 进制数，因为每堆牌的剩余数量可以是 0 到 4。
• 初始状态（所有牌都在）的编码为 (4 \times 5^8 + 4 \times 5^7 + \dots + 4 \times 5^0 = 1953124)。
• 输出保留 6 位小数。