一个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 = ;
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 = ; i <= n; i++)
for (int j = ; j <= m; j++)
for (int k = ; k <= sum; k++)
dp[i][j][k] = ;
dp[][][] = 1.0;
for (int k = ; k <= sum; k++)
{
for (int i = ; i <= n; i++)
{
for (int j = ; j <= m; j++)
{
dp[i][j][k] += dp[i][j][k - ] * ((i * j - k + ) * 1.0 / (sum - k + ));//新添加的位置没有新增加行和列,所以他的概率就是(还剩下多少个符合不增加行和列能填的格子)/总的能填的格子
dp[i][j][k] += dp[i - ][j][k - ] * ((n - i + ) * j * 1.0 / (sum - k + ));//同理增加行不增加列
dp[i][j][k] += dp[i][j - ][k - ] * (i * (m - j + ) * 1.0 / (sum - k + ));//增加列不增加行
dp[i][j][k] += dp[i - ][j - ][k - ] * ((n - i + ) * (m - j + ) * 1.0 / (sum - k + ));//增加行和列
}
}
}
double ans = ;
for (int k = ; k <= sum; k++)
ans += (dp[n][m][k] - dp[n][m][k - ]) * k;//第k天刚好填满n和m所以就是dp[n][m][k] - dp[n][m][k - 1]
printf("%.10f\n", ans); } return ;
}