本文共 1320 字，大约阅读时间需要 4 分钟。
题意：36张扑克，平分成9摞，两张数字一样的可以拿走，每次随机拿两张，问能拿光的概率。
解法：记忆化搜索，状态压缩。一开始我想在还没拿的时候概率是1，然后往全拿光推···样例过不去···后来觉得推反了，改成了深搜，模拟拿牌的过程，九摞牌的状态用9位五进制表示。
代码：
#include #include #include #include #include #include #include #include #include #include #include #include #include #include #define LL long longusing namespace std;double dp[2000000];int vis[2000000];char card[9][5][3];double dfs(int n){ if(n == 0) return 1.0; if(vis[n]) return dp[n]; vis[n] = 1; int a[10]; int tmp = n; for(int i = 0; i < 9; i++) { a[i] = tmp % 5; tmp /= 5; } int cnt = 0; for(int i = 0; i < 9; i++) for(int j = i + 1; j < 9; j++) if(a[i] && a[j] && card[i][a[i]][0] == card[j][a[j]][0]) { //cout << "i = " << i << " j = " << j << endl; tmp = 0; for(int k = 8; k >= 0; k--) { tmp *= 5; if(k == i || k == j) tmp += a[k] - 1; else tmp += a[k]; } dp[n] += dfs(tmp); cnt++; } if(cnt) dp[n] /= (double)cnt; return dp[n];}int main(){ while(~scanf("%s", card[0][1])) { for(int i = 2; i < 5; i++) scanf("%s", card[0][i]); for(int i = 1; i < 9; i++) for(int j = 1; j < 5; j++) scanf("%s", card[i][j]); memset(dp, 0, sizeof(dp)); memset(vis, 0, sizeof(vis)); double ans = dfs(1953124); printf("%.6lf\n", ans); } return 0;}
转载于:https://www.cnblogs.com/Apro/p/4303980.html