1637：概率 DP + Map 狀態壓縮

題目大意

9 堆牌，每堆 4 張，共 36 張。每次隨機選兩堆牌頂相同則移除。求能否移除所有牌的概率。

狀態表示

狀態 = 9 維向量，第 i 維為第 i 堆剩餘牌數（0…4）。
用 vector<int> 作 key，map<vector<int>, double> 記憶化。

遞歸轉移

double dp(vector<int> &cnt, int remain) {
    if (remain == 0) return 1.0;
    if (memo.count(cnt)) return memo[cnt];
    double sum = 0; int tot = 0;
    for (int i = 0; i < 9; ++i) if (cnt[i])
        for (int j = i+1; j < 9; ++j) if (cnt[j])
            if (top[i][cnt[i]-1] == top[j][cnt[j]-1]) {
                ++tot;
                cnt[i]--; cnt[j]--;
                sum += dp(cnt, remain - 2);
                cnt[i]++; cnt[j]++;
            }
    if (tot == 0) return memo[cnt] = 0;
    return memo[cnt] = sum / tot;
}

完整代碼

#include <bits/stdc++.h>
using namespace std;
map<vector<int>, double> memo;
char card[9][4][3];
double solve(vector<int> cnt, int rem) {
    if (rem == 0) return 1;
    if (memo.count(cnt)) return memo[cnt];
    double sum = 0; int tot = 0;
    for (int i = 0; i < 9; ++i) if (cnt[i])
        for (int j = i+1; j < 9; ++j) if (cnt[j])
            if (card[i][cnt[i]-1][0] == card[j][cnt[j]-1][0]) {
                ++tot;
                cnt[i]--; cnt[j]--;
                sum += solve(cnt, rem - 2);
                cnt[i]++; cnt[j]++;
            }
    if (tot == 0) return memo[cnt] = 0;
    return memo[cnt] = sum / tot;
}
int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    while (true) {
        bool ok = true;
        for (int i = 0; i < 9; ++i)
            for (int j = 0; j < 4; ++j)
                if (!(cin >> card[i][j])) { ok = false; break; }
        if (!ok) break;
        vector<int> cnt(9, 4);
        memo.clear();
        cout << fixed << setprecision(6) << solve(cnt, 36) << '\n';
    }
    return 0;
}

關鍵點

• vector 可直接作 map key，自動按字典序比較。
• 狀態數遠小於 5⁹ ≈ 195 萬，實際可達態約幾萬，記憶化極快。
• 全概率公式：每種可行轉移等概率，遞歸邊界剩 0 張牌概率 1。