zoj 3822 Domination(dp)
2024-10-15 13:06:24
题目大意:给定一个N∗M的棋盘,每次任选一个位置放置一枚棋子,直到每行每列上都至少有一枚棋子,问放置棋子个数的期望。
解题思路:大白书上概率那一张有一道类似的题目,可是由于时间比較久了,还是略微想了一下。
dp[i][j][k]表示i行j列上均有至少一枚棋子,而且消耗k步的概率(k≤i∗j),由于放置在i+1~n上等价与放在i+1行上,同理列也是如此。所以有转移方程:
- dp[i][j][k+1]+=dp[i][j][k]∗(n−k)(S−k)
- dp[i+1][j][k+1]+=dp[i][j][k]∗(N−i)∗j(S−k)
- dp[i][j+1][k+1]+=dp[i][j][k]∗(M−j)∗i(S−k)
- dp[i+1][j+1][k+1]+=dp[i][j][k]∗(N−i)∗(M−j)(S−k)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 55;
const int maxm = 2505;
int N, M;
double dp[maxn][maxn][maxm];
double solve () {
int S = 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++) {
int n = i * j;
for (int k = max(i, j); k <= n; k++) {
dp[i][j][k+1] += dp[i][j][k] * (n - k) / (S - k);
dp[i+1][j][k+1] += dp[i][j][k] * (N - i) * j / (S - k);
dp[i][j+1][k+1] += dp[i][j][k] * (M - j) * i / (S - k);
dp[i+1][j+1][k+1] += dp[i][j][k] * (N - i) * (M - j) / (S - k);
}
}
}
/*
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= M; j++) {
printf("%d %d:", i, j);
for (int k = max(i, j); k <= i * j; k++)
printf("%.3lf ", dp[i][j][k]);
printf("\n");
}
}
*/
double ans = 0;
for (int i = max(N, M); i <= S; i++)
ans += (dp[N][M][i] - dp[N][M][i-1]) * i;
return ans;
}
int main () {
int cas;
scanf("%d", &cas);
while (scanf("%d%d", &N, &M) == 2) {
printf("%.8lf\n", solve());
}
return 0;
}
最新文章
- 5分钟部署ELK+filebeat5.1.1
- Linux 下安装中文 ctex 指南
- Vim 快速上手
- CSS第四天总结 更多的属性 圆角 边框图片 段落属性 颜色渐变 盒子阴影
- WebJars 进行 css js 资源文件管理
- FastSocket.Net
- push 栈顶sp=sp-2 可以把立着的栈,向左侧倒下,那么形态就和反汇编时,内存的形态是一样的。小偏移的字节在前, 大的偏移字节在后
- javascript 写农场迭代
- FireMonkey隐藏任务栏图标
- makefile 进阶
- python之加密
- linux下U盘的读取
- opencv 图像仿射变换 计算仿射变换后对应特征点的新坐标 图像旋转、缩放、平移
- PHP判断是中文还是英文
- cocos2d-x游戏开发系列教程-超级玛丽02-代码结构
- angularJS在创建指令需要注意的问题(指令中使用ngRepeat)
- (中等) POJ 1054 The Troublesome Frog,记忆化搜索。
- 【JAVA】杨辉三角
- jmeter(十八)关联之XPath Extractor
- Git冲突与解决方法【转】
热门文章
- 【.NET进程通信】初探.NET中进程间通信的简单的实现
- 3.cocos2dx它Menu,由menu为了实现场景切换
- 拆除vs发展c++程序开发过程中产生的.ipch和.sdf文件的方法
- Android于JNI调用列出的程序
- ExtJs--02--MessageBox相关弹出窗口alert,prompt,confirm采用
- rest服务器
- 快讯:埃博拉患者Martin Salia去天堂了
- secureCRT使用退格键(backspace)出现^H解决的方法
- hdu 5045 费用流
- java它们的定义jar套餐读Excel(这包括2003和2007)数据,和实例