一个n行m列的棋盘，每天可以放一个棋子，问要使得棋盘的每行每列都至少有一个棋子 需要的放棋子天数的期望。
dp[i][j][k]表示用了k天棋子共能占领棋盘的i行j列的概率。
他的放置策略是，每放一次，就会有四种可能
1）增加一行一列
2）增加一行
3)增加一列
4）不变
所以他放置的概率就可以求出来，每次放下的概率就是当前能放的点除以总的空的点数。
最后统计期望的时候需要统计在第k天刚好符合占满n行m列的概率，就是dp[i][j][k]-dp[i][j][k-1]
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn = 52; double dp[maxn][maxn][maxn*maxn]; int main() { int T; scanf("%d", &T); while (T--) { int n, m; scanf("%d %d", &n, &m); int sum = n * m; for (int i = 0; i <= n; i++) for (int j = 0; j <= m; j++) for (int k = 0; k <= sum; k++) dp[i][j][k] = 0; dp[0][0][0] = 1.0; for (int k = 1; k <= sum; k++) { for (int i = 1; i <= n; i++) { for (int j = 1; j <= m; j++) { dp[i][j][k] += dp[i][j][k - 1] * ((i * j - k + 1) * 1.0 / (sum - k + 1));//新添加的位置没有新增加行和列,所以他的概率就是(还剩下多少个符合不增加行和列能填的格子)/总的能填的格子 dp[i][j][k] += dp[i - 1][j][k - 1] * ((n - i + 1) * j * 1.0 / (sum - k + 1));//同理增加行不增加列 dp[i][j][k] += dp[i][j - 1][k - 1] * (i * (m - j + 1) * 1.0 / (sum - k + 1));//增加列不增加行 dp[i][j][k] += dp[i - 1][j - 1][k - 1] * ((n - i + 1) * (m - j + 1) * 1.0 / (sum - k + 1));//增加行和列 } } } double ans = 0; for (int k = 1; k <= sum; k++) ans += (dp[n][m][k] - dp[n][m][k - 1]) * k;//第k天刚好填满n和m所以就是dp[n][m][k] - dp[n][m][k - 1] printf("%.10f ", ans); } return 0; }