ZOJ 3822 Domination 概率DP

题意:在一个n*m的棋盘上放棋子,一个棋子可覆盖一行一列,若n行m列全被覆盖则停止放棋子,求棋子的期望

思路:期望DP, dp[i][j][k]表示放了i个棋子覆盖了j行k列

已知dp[0][0][0]=1,求dp[1~n*m][n][m]

四种情况:

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;
}
时间: 03-14

ZOJ 3822 Domination 概率DP的相关文章

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

[概率dp] zoj 3822 Domination

题目链接: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3822 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 che

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

ZOJ 3822 Domination DP

状态i,j,k为已经有i行,j列放满,放了k个棋子的概率,转移分四种情况(只增加行,只增加列,行列都增加,行列都不增加)讨论即可. #include <cstdio> #include <cstring> #include <algorithm> #include <queue> #include <stack> #include <map> #include <set> #include <climits>