Time Limit: 8 Seconds Memory Limit: 131072 KB Special Judge
Edward is the headmaster of Marjar University. He is enthusiastic about chess and often plays chess with his friends. What's more, he bought a large decorative chessboard with N rows and M columns.
Every day after work, Edward will place a chess piece on a random empty cell. A few days later, he found the chessboard was dominated by the chess pieces. That means there is at least one chess piece in every row. Also, there is at least one chess piece in every column.
"That's interesting!" Edward said. He wants to know the expectation number of days to make an empty chessboard of N × M dominated. Please write a program to help him.
Input
There are multiple test cases. The first line of input contains an integer T indicating the number of test cases. For each test case:
There are only two integers N and M (1 <= N, M <= 50).
Output
For each test case, output the expectation number of days.
Any solution with a relative or absolute error of at most 10-8 will be accepted.
Sample Input
2 1 3 2 2
Sample Output
3.000000000000 2.666666666667
题意:
给出 T 组样例,每组样例有 N,M 两个数,代表 N 行 M 列。每次往棋盘放一只棋子,每个棋子可以覆盖所在行与列,输出放多少个棋子能覆盖整个棋盘的数学期望。
思路:
概率 DP。dp [ i ] [ j ] [ k ] 代表用 k 只棋子覆盖了 i 行,j 列(任意行,任意列,代表的是有 i 行,有 j 列而不是特指某 i 行,某 j 列)。转移方程的时候注意要分开讨论,因为如果当 i == n && j == m 的时候,如果之前已经是覆盖了的就不需要加上 dp [ i ] [ j ] [ k - 1 ] * (i * j - (k - 1)) / ( n * m - k + 1 ) 的概率了。
AC:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int N = 55; const int MAX = N * N; double dp[N][N][MAX]; int main() { int t; scanf("%d", &t); while (t--) { int n, m; scanf("%d%d", &n, &m); double sum = n * m; memset(dp, 0, sizeof(dp)); dp[0][0][0] = 1.0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { for (int k = 1; k <= sum; ++k) { double left = sum - (k - 1); double p1 = (i * j - (k - 1)) / left; double p2 = (n - (i - 1)) * j / left; double p3 = (m - (j - 1)) * i / left; double p4 = (n - (i - 1)) * (m - (j - 1)) / left; if (i == n && j == m) { dp[i][j][k] += dp[i - 1][j][k - 1] * p2; dp[i][j][k] += dp[i][j - 1][k - 1] * p3; dp[i][j][k] += dp[i - 1][j - 1][k - 1] * p4; } else { dp[i][j][k] += dp[i][j][k - 1] * p1; dp[i][j][k] += dp[i - 1][j][k - 1] * p2; dp[i][j][k] += dp[i][j - 1][k - 1] * p3; dp[i][j][k] += dp[i - 1][j - 1][k - 1] * p4; } } } } double res = 0; for (int i = 0; i <= sum; ++i) { res += dp[n][m][i] * i; } printf("%.12lf\n", res); } return 0; }
相关推荐
基于java的开发源码-lobby(经典board游戏 Domination).zip 基于java的开发源码-lobby(经典board游戏 Domination).zip 基于java的开发源码-lobby(经典board游戏 Domination).zip 基于java的开发源码-lobby(经典board...
lobby(经典board游戏 Domination)
将任务文件夹co30_Domination.Altis复制到本地mpmission目录中 将任务加载到Eden编辑器中,然后单击“播放” ->“多人游戏” ->“确定”以运行您的本地代码 编辑任务 统治任务可以在伊甸园编辑器中进行修改。 ...
带精英决策的多目标优化关键程序,希望对大家有用。
基于Java的lobby(经典board游戏 Domination).zip
基于java的lobby(经典board游戏 Domination).zip
java源码:lobby(经典board游戏 Domination).rar
基于Java的源码-lobby(经典board游戏 Domination).zip
藏经阁-Evading-MicrosoftATA-for-ActiveDirectory-Domination
On Upper Total Domination Versus Upper Domination in Graphs
基于Java的实例开发源码-lobby(经典board游戏 Domination).zip
WorDoG代表世界统治游戏。 它类似于流行的棋盘游戏《 Risk》。 该项目旨在提供仅基于html的战略多人战略游戏。 所有必要的操作都是通过PHP和数据库在服务器端完成的。
统治不和谐机器人DomiNATION Discord Bot是为创建的机器人。 这是我的第一个项目,激发了我对软件开发的兴趣。 自开始以来,我已经注册并完成了代码训练营,成为了Full Stack Java Developer! Java版DomiNATION ...
On the domination number of generalized Petersen graphs P(ck,k)
Independent rainbow domination of graphs
一种用Java编写的联网的,二维,多平台,多人射击游戏,其中,玩家试图捕获并保持对基地的控制以便获得积分。
来自 Brad Callen 的搜索引擎优化专业指导
On the semitotal domination number of line graphs
lobby(经典board游戏 Domination)源码
免责声明:资料部分来源于合法的互联网渠道收集和整理,部分自己学习积累成果,供大家学习参考与交流。收取的费用仅用于收集和整理资料耗费时间的酬劳。 本人尊重原创作者或出版方,资料版权归原作者或出版方所有,...