ZOJ 3822 Domination 概率DP

1.再放一个棋子，行列都不增加

dp[i+1][j][k]+=dp[i][j][k]*(j*k-i)*1.0/(m*n-i);

2.只增加一行

dp[i+1][j+1][k]+=dp[i][j][k]*(n-j)*k*1.0/(m*n-i);

3.只增加一列

dp[i+1][j][k+1]+=dp[i][j][k]*(m-k)*j*1.0/(m*n-i);

4.增加了一行一列

dp[i+1][j+1][k+1]+=dp[i][j][k]*((m-k)*(n-j))*1.0/(m*n-i);

```#include <iostream>
#include <queue>
#include <stack>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cstdlib>
#include <cmath>
#include <cstdio>
using namespace std;
double dp[2505][55][55];
int main()
{
int T,n,m,i,j,k;
double ans;
scanf("%d",&T);
while(T--)
{
scanf("%d%d",&n,&m);
memset(dp,0,sizeof(dp));
dp[0][0][0]=1.0;
for(i=0;i<=n*m;i++)
{
for(j=0;j<=n;j++)
{
for(k=0;k<=m;k++)
{
if(j==n&&k==m) continue;
dp[i+1][j][k]+=dp[i][j][k]*(j*k-i)*1.0/(m*n-i);

dp[i+1][j+1][k]+=dp[i][j][k]*(n-j)*k*1.0/(m*n-i);

dp[i+1][j][k+1]+=dp[i][j][k]*(m-k)*j*1.0/(m*n-i);

dp[i+1][j+1][k+1]+=dp[i][j][k]*((m-k)*(n-j))*1.0/(m*n-i);
}
}
}
ans=0;
for(i=0;i<=n*m;i++)
ans+=i*dp[i][n][m];
printf("%.8f\n",ans);
}
return 0;
}```

zoj 3288 Domination (概率dp)

///dp[i][j][k]表示i行j列已经有棋子,且放了k个的概率 ///dp[i][j][k]一共有四种转移方式 ///1:dp[i-1][j][k-1] 概率为 (n-(i-1))*j/(n*m-(k-1)) ///2:dp[i][j-1][k-1] 概率为 i*(m-(j-1))/(n*m-(k-1)) ///3:dp[i-1][j-1][k-1] 概率为 (n-(i-1))*(m-(j-1))/(n*m-(k-1)) ///4:dp[i][j][k-1] 概率为 (i*j-(k-1))

ZOJ - 3822 Domination （DP）

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 piec

zoj 3822 Domination 【概率DP 求期望】

Domination 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 chessboar

14牡丹江现场赛 D ZOJ 3822 Domination

Domination 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 chessboar

ZOJ 3822 Domination (三维概率DP)

E - Domination Time Limit:8000MS     Memory Limit:131072KB     64bit IO Format:%lld & %llu Submit Status Description Edward is the headmaster of Marjar University. He is enthusiastic about chess and often plays chess with his friends. What's more, he

ZOJ 3822 Domination （概率DP）

Domination 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 chessboar

ACM学习历程——ZOJ 3822 Domination （2014牡丹江区域赛 D题）（概率，数学递推）

Description 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