首页 > 代码库 > [Codefoeces398B]Painting The Wall(概率DP)
[Codefoeces398B]Painting The Wall(概率DP)
题目大意：一个$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)}$$
代码：
1 #include<cstring> 2 #include<cstdio> 3 #include<algorithm> 4 #include<cmath> 5 #define foru(i,x,y) for(int i=x;i<=y;i++) 6 using namespace std; 7 typedef double db; 8 const int N=2010; 9 db f[N][N];10 int br[N],bc[N],n,m,x,y,r,c;11 int main(){12 scanf("%d%d",&n,&m);13 r=c=n;14 foru(i,1,m){15 scanf("%d%d",&x,&y);16 if(!br[x])br[x]=1,r--;17 if(!bc[y])bc[y]=1,c--;18 }19 f[0][0]=0;20 foru(i,1,n){21 f[i][0]=f[i-1][0]+(db)n/i;22 f[0][i]=f[0][i-1]+(db)n/i;23 }24 foru(i,1,r)25 foru(j,1,c){26 f[i][j]=(db)n*n+(i*j*f[i-1][j-1]+i*(n-j)*f[i-1][j]+(n-i)*j*f[i][j-1]);27 f[i][j]/=(n*n-(n-i)*(n-j));28 }29 printf("%.10lf\n",f[r][c]);30 }
[Codefoeces398B]Painting The Wall(概率DP)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。