[Codefoeces398B]Painting The Wall(概率DP)
2024-09-07 06:52:47
题目大意:一个$n\times n$的棋盘,其中有$m$个格子已经被染色,执行一次染色操作(无论选择的格子是否已被染色)消耗一个单位时间,染色时选中每个格子的概率均等,求使每一行、每一列都存在被染色的格子的期望用时。
显然,被染色的砖的位置对解题是没有影响的,我们可以将已染色砖所在的行和列移动到右下角,问题就转化到了在更小棋盘中的新问题。
在任一时刻,棋盘内的状态如下:
其中绿色区域为当前问题的棋盘,选中对行和列都有贡献;
选中黄色对行或列有贡献;
选中红色没有贡献;
设$f[i][j]$表示剩余$i$行$j$列未染色,则$$f[i][j]=\frac {i\times j\times f[i-1][j-1]+i\times (n-j)\times f[i-1][j]+(n-i)\times j\times f[i][j-1]+(n-i)\times (n-j)\times f[i][j]} {n^2}$$
两边都有$f[i][j]$,化简得:$$f[i][j]=\frac {n^2+i\times j\times f[i-1][j-1]+i\times (n-j)\times f[i-1][j]+(n-i)\times j\times f[i][j-1]} {n^2-(n-i)\times (n-j)}$$
代码:
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
#define foru(i,x,y) for(int i=x;i<=y;i++)
using namespace std;
typedef double db;
const int N=;
db f[N][N];
int br[N],bc[N],n,m,x,y,r,c;
int main(){
scanf("%d%d",&n,&m);
r=c=n;
foru(i,,m){
scanf("%d%d",&x,&y);
if(!br[x])br[x]=,r--;
if(!bc[y])bc[y]=,c--;
}
f[][]=;
foru(i,,n){
f[i][]=f[i-][]+(db)n/i;
f[][i]=f[][i-]+(db)n/i;
}
foru(i,,r)
foru(j,,c){
f[i][j]=(db)n*n+(i*j*f[i-][j-]+i*(n-j)*f[i-][j]+(n-i)*j*f[i][j-]);
f[i][j]/=(n*n-(n-i)*(n-j));
}
printf("%.10lf\n",f[r][c]);
}
最新文章
- java基础知识(十一)java反射机制(下)
- iOS团队风格的统一
- Android Studio中使用android:src=";@drawable/ic_launcher";报错
- 【自动化测试】Xpath学习
- MFC下拉框使用方法
- php如何修改SESSION的生存时间
- poj 2723 Get Luffy Out(2-sat)
- MYSQL truncate table
- Jni Tips
- apicloud
- python 之分发包
- C语言诠释--为什么内存是线性分布的。
- c++继承学习
- [Swift]LeetCode673. 最长递增子序列的个数 | Number of Longest Increasing Subsequence
- HUSTOJ:5500 &;&; 洛谷:P1412:经营与开发
- 记一次ORACLE无法启动登陆事故
- Blog Part I
- 剑指Offer 19. 顺时针打印矩阵 (其他)
- Amazon RDS 上的 Microsoft SQL Server &#187; 导入和导出 SQL Server 数据库
- Git clone 常见用法
热门文章
- git本地仓库连接同步修改远程仓库
- (day 1)创建项目--1
- cpu压测测试--------自己设定cpu需要跑到的压力
- 7206VXR系列板卡简介(转)
- python交互图
- 通过实例说明在scrapy中 yield的作用
- UML-什么是GRASP?
- 关于WIN7系统,在运行pycharm时,老出现问题
- 2019 Python工程师平均薪资22K,又涨了11.9%!
- java.sql.BatchUpdateException: ORA-01691: Lob 段 CSASSSMBI.SYS_LOB0000076987C00003$$ 无法通过 128 (在表空间 HRDL_CSASS 中) 扩展