这题说得是给了一个n*m的棋盘，每天在这个棋盘中放置一个棋子，不能放在之前已经摆放过得地方，求最后使得每行每列都有至少一个棋子的期望天数是多少，这样我们考虑怎么放，放哪里，显然数据大而且不知道状态怎么表示， 考虑现在有i行j列放有k个棋子 这样我们要求的概率就是dp[n][m][k],表示n行m列有棋子棋子个数为k
那么 dp[i][j][k] 会从 1扩展行 2扩展列 3 同时扩展行和列，4 行列 都不扩展， 相应的求出其概率
#include<map> #include<set> #include<list> #include<cmath> #include<ctime> #include<deque> #include<stack> #include<queue> #include<cstdio> #include<bitset> #include<string> #include<vector> #include<cstdlib> #include<cstring> #include<ctype.h> #include<complex> #include<fstream> #include<iomanip> #include<numeric> #include<sstream> #include<iostream> #include<algorithm> #include<functional> using namespace std; typedef long long LL; const int MOD = 1e9 + 7; const double EPS = 1e-9; const int MAXN = 1e5 + 5; const int INF = 0x7fffffff; const double PI = acos(-1.0); typedef unsigned long long uLL; int n, m, ans = -1; double dp[55][55][55 * 50]; int main() { int cas; scanf("%d", &cas); while(cas--){ int n, m; scanf("%d%d", &n, &m); memset(dp, 0, sizeof(dp)); dp[1][1][1] = 1; int cnt = n*m; for(int i = 1; i <= n; ++i) for(int j = 1; j <= m; ++j) for(int num = max(i, j); num <= i*j; ++num) { dp[i][j][num] += dp[i - 1][j][num - 1] * (n - i + 1)*j / (cnt - num + 1); dp[i][j][num] += dp[i][j - 1][num - 1] * (m - j + 1)*i / (cnt - num + 1); dp[i][j][num] += dp[i - 1][j - 1][num - 1] * (cnt - (i - 1)*m - (j - 1)*n + (i - 1)*(j - 1)) / (cnt - num + 1); if(i==n&&j==m) continue; dp[i][j][num] += dp[i][j][num - 1] * (i*j - num + 1) / (cnt - num + 1); } double ans = 0; int tt = n*m;// max(n*(m - 1) + 1, (n - 1)*m + 1); for(int i = 1; i <= tt; ++i) ans += dp[n][m][i] * i; printf("%.12lf ", ans); } return 0; }