1637

一道狀態較多的概率DP，想要表示所有的狀態顯然要拓展幾個維度表示九堆牌當前的狀態 。

但是這麼寫太復雜，所以我們不妨用一個vector來儲存狀態，將dp數組用一個map來表示，即 map ,double> d; 利用vector可以作為函數參數傳遞這個優點，將大大節省代碼量 。

概率很好求，在每一次迭代中，尋找所有可以轉移的狀態數tot，那麼狀態轉移就是d[i] = sum(d[i-1])/tot 。 也就是全概率公式 。

遞歸邊界是當所有牌都被摸走了，返回1（因為概率總和為1）。

全概率公式說白了就是每一部分都不相交，且相加恰好為1 。 其實對於概率DP，所求的概率一定是全概率的，因為DP所表示的每一個狀態的概率是一個固定的值，且相加為1。

由此也可以看出，如果運用動態規劃，那麼必須滿足：狀態經過多次轉移之後不會回到以前的狀態 。

細節參見代碼：

#include
using namespace std;
map ,double> d;
char s[15][15][5];
double dp(vector cnt,int c) {
    if(c == 0) return 1;
    if(d.count(cnt)) return d[cnt];
    double sum = 0;
    int tot = 0;
    for(int i=0;i<9;i++) if(cnt[i]>0)
        for(int j=i+1;j<9;j++) if(cnt[j]>0)
            if(s[i][cnt[i]-1][0] == s[j][cnt[j]-1][0]) {
                tot++;
                cnt[i]--; cnt[j]--;
                sum += dp(cnt,c-2);
                cnt[i]++; cnt[j]++;
            }
    if(tot == 0) return d[cnt] = 0;
    return d[cnt] = sum/tot;
}
bool read_input() {
    for(int i=0;i<9;i++)
        for(int j=0;j<4;j++)
        if(scanf(%s,s[i][j]) != 1) return false;
    return true;
}
int main() {
    while(read_input()) {
        vector cnt(9,4);
        d.clear();
        printf(%.6f
,dp(cnt,36));
    }
    return 0;
}