Domination Gym - 100554D(概率dp 求期望)

题意

1. 给我们一个 n*m 的棋盘，每天我们会在棋盘上放一个棋子，问使每一行每一列至少有一个棋子所需要的期望天数是多少？

思路

1. 直接求期望，不太好 dp
2. 但是我们可以通过期望求解公式：E (X) = X1p(X1） + X2p (X2） + …… + Xn*p (Xn) 来求解。
3. 我们设状态转移方程：dp [i][j][k] 表示棋子 i 行 j 列已经有棋子占领了，在摆放 k 个棋子的时候的概率。
4. 初始状态：dp [1][1][1] = 1.0
5. 我们通过递推进行状态转移对于 dp [i][j][k] 可以递推出：dp [i][j][k+1]、dp [i+1][j][k+1]、dp [i][j+1][k+1]、dp [i+1][j+1][k]
6. 那么期望就是：E (X) = 1 * dp [n][m][1]+2 * dp [n][m][2] + …… + k*dp [n][m][k]…

代码

#include <bits/stdc++.h>
using namespace std;
const int N = 55;
int n, m;
double dp[N][N][N * N];
int main()
{
int T; scanf("%d", &T);
while (T --)
{
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)
//这个特判必须要加
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] * i * (m - j) / (n * m - k);
dp[i + 1][j + 1][k + 1] += dp[i][j][k] * (n - i) * (m - j) / (n * m - k);
}
double ans = 0;
for (int i = 1; i <= n * m; i ++) {
ans += dp[n][m][i] * i;
}
printf("%.12fn", ans);
}
return 0;
}

最后

以上就是无辜寒风为你收集整理的Domination Gym - 100554D(概率dp 求期望)的全部内容，希望文章能够帮你解决Domination Gym - 100554D(概率dp 求期望)所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。