6
2025-08-10 16:07:40
发布于:江苏
#include<bits/stdc++.h>
using namespace std;
const int N_STATES = 1953125;
vector<double> dp(N_STATES, -1.0);
vector<vector<string>> piles(9, vector<string>(4));
vector<long> pow5(9);
double dfs(int state) {
if (dp[state] >= 0) {
return dp[state];
}
vector<int> remain(9);
int s = state;
for (int i = 0; i < 9; i++) {
remain[i] = s % 5;
s /= 5;
}
double total_prob = 0.0;
int moves = 0;
for (int i = 0; i < 9; i++) {
if (remain[i] == 0) continue;
for (int j = i + 1; j < 9; j++) {
if (remain[j] == 0) continue;
if (piles[i][remain[i]-1][0] != piles[j][remain[j]-1][0]) continue;
vector<int> new_remain = remain;
new_remain[i]--;
new_remain[j]--;
int new_state = 0;
for (int k = 0; k < 9; k++) {
new_state += new_remain[k] * pow5[k];
}
total_prob += dfs(new_state);
moves++;
}
}
if (moves > 0) {
dp[state] = total_prob / moves;
} else {
dp[state] = 0.0;
}
return dp[state];
}
int main() {
pow5[0] = 1;
for (int i = 1; i < 9; i++) {
pow5[i] = pow5[i-1] * 5;
}for (int i = 0; i < 9; i++) {
for (int j = 0; j < 4; j++) {
cin >> piles[i][j];
}
}
int init_state = 0;
for (int i = 0; i < 9; i++) {
init_state += 4 * pow5[i];
}
dp[0] = 1.0;
double ans = dfs(init_state);
cout << fixed << setprecision(6) << ans << endl;
return 0;
}
这里空空如也
有帮助,赞一个