首页 > 代码库 > 2014牡丹江——Domination
2014牡丹江——Domination
题目链接
- 题意:
给一个n*m的矩阵,每天随机的在未放棋子的格子上放一个棋子。求每行至少有一个棋子,每列至少有一个棋子的天数的期望
(1 <= N, M <= 50). - 分析:
比较明显的概率DP,难点在于如何设计状态。覆盖了多少行和列是必不可少的,之后比较关键的就是想到另一个属性:多少个交叉点(即放过的点)
double dp[55][55][2550]; bool vis[55][55][2550]; int tot; int n, m; inline double getp(int xx, int yy) { return (xx * 1.0) / yy; } double dpf(int x, int y, int z) { if (x > n || y > m || z > tot) return 0; if (x == n && y == m) return 0.0; if (vis[x][y][z]) return dp[x][y][z]; vis[x][y][z] = true; int a = x * y - z; int b = tot - (x * m + y * n - x * y); int xc = x * m - x * y; int yc = y * n - x * y; int sum = a + b + xc + yc; dp[x][y][z] = 0; if (a) dp[x][y][z] += getp(a, sum) * dpf(x, y, z + 1); if (b) dp[x][y][z] += getp(b, sum) * dpf(x + 1, y + 1, z + 1); if (xc) dp[x][y][z] += getp(xc, sum) * dpf(x, y + 1, z + 1); if (yc) dp[x][y][z] += getp(yc, sum) * dpf(x + 1, y, z + 1); dp[x][y][z] += 1.0; return dp[x][y][z]; } int main() { int T; RI(T); while (T--) { RII(n, m); tot = n * m; memset(vis, 0, sizeof(vis)); printf("%.12lf\n", dpf(0, 0, 0)); } return 0; }
2014牡丹江——Domination
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。