Gym - 100554D Domination (概率DP)

题目链接

题意:给出一个t，表示t组数据，之后每组数据一个n，m表示棋盘的行数和列数，题目背景是一个人每次会随机向棋盘上一格放一个棋子,问每行每列都最少有一个棋子的数学期望是多少?

//eg：2         
//       1 3    =》    3.000000000000
//       2 2    =》    2.666666666667

题解:

         概率dp，用dp[i][j][k]表示第k天有i行j列存在棋子的概率，得到下面的状态转移方程，算出dp[n][m][]后乘上对应天数求和即为数学期望.

代码如下:

#include<iostream>
#include<cstring>
#include<string>
#include<cstdio>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<algorithm>
using namespace std;
#define inf 0x3f3f3f3f
#define ll long long
const int maxn = 2e5 + 100;
double dp[55][55][55 * 55];
int main()
{
	int t;
	scanf("%d", &t);
	while (t--)
	{
		int n, m;
		scanf("%d%d", &n, &m);
		memset(dp, 0, sizeof(dp));
		dp[1][1][1] = 1;
		for (int i = 1; i <= n; i++)
			for (int j = 1; j <= m; j++)
				for (int k = 1; k <= i*j; k++)
				{
					if (i<n || j<m) //若不加这个if结果会出错，因为当i==n，j==m时再进行这条dp会对所有最终答案的数据进行修改，而下面三条不会
						dp[i][j][k + 1] += dp[i][j][k] * (i*j - k) / (n*m - k);
					dp[i + 1][j][k + 1] += dp[i][j][k] * (n - i)*j / (n*m - k);
					dp[i][j + 1][k + 1] += dp[i][j][k] * (m - j)*i / (n*m - k);
					dp[i + 1][j + 1][k + 1] += dp[i][j][k] * (n - i)*(m - j) / (n*m - k);
				}
		double sum = 0.0;
		for (int i = 1; i <= n*m; i++)
			sum += dp[n][m][i] * i;
		printf("%.12f\n", sum);
	}
	return 0;
}