Domination（概率DP)

Domination

题目链接:https://odzkskevi.qnssl.com/9713ae1d3ff2cc043442f25e9a86814c?v=1531624384

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 piece on a random empty cell. A few days later, he found the chessboard was dominated by the chess pieces. That means there is at least one chess piece in every row. Also, there is at least one chess piece in every column.

"That's interesting!" Edward said. He wants to know the expectation number of days to make an empty chessboard of N × M dominated. Please write a program to help him.

Input

There are multiple test cases. The first line of input contains an integer Tindicating the number of test cases. For each test case:

There are only two integers N and M (1 <= N, M <= 50).

Output

For each test case, output the expectation number of days.

Any solution with a relative or absolute error of at most 10^-8 will be accepted.

Sample Input

2
1 3
2 2

Sample Output

3.000000000000
2.666666666667


题意： 给出一个n*m的棋盘，问下棋下到每行每列均有一个棋的情况步数的期望值

思路： 这个数据虽然不大，但是搜索那些肯定是不行的，但是我们又要列出所有的情况，就只能用记忆化搜索，
期望值就是每个步数的概率乘以这个步数之和，所以我们要求出每个步数分别的概率是多少，在这里我们使用三维dp
dp[i][j][k] 代表的是k个棋已经占了i行j列，保证i行并且j列里面都会有一个棋
然后我们想下怎么推导呢想一下，我们每多下一个棋，有四种可能
第一种 多占了一列
第二种 多占了一行
第三种 下在对角线，占一行一列
第四种 下在了之前已经占过的行列上
就可以推导出式子dp[i][j][k]=dp[i][j-1][k-1]+dp[i-1][j][k-1]+dp[i-1][j-1][k-1]+dp[i][j][k-1];
这四种可能的和，但是我下棋的时候每个情况有多少个位置可以下，这里也要求下概率
占一行（意思是这个棋的列要下在之前占过的列的位置，因为要新占一行，所以选的行就是剩下没被占过的数量，然后再除以总的剩下可以下的位置）
其他的以此类推
然后dp数组就存的是概率，我们再去枚举那个占了整个棋盘的概率dp[n][m][i]*i即可
大佬博客：https://blog.csdn.net/cq_pf/article/details/48393897

#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
double dp[55][55][55*55];
int n,m;
void solve()
{
    memset(dp,0,sizeof(dp));
    dp[0][0][0]=1.0;
    for(int i=1;i<=n;i++)//枚举行
    {
        for(int j=1;j<=m;j++)//枚举列
        {
            for(int k=1;k<=n*m;k++)//枚举下的棋子个数
            {
                if(i==n&&j==m)//下最后一个棋的时候没有既不占列也不占行的可能性
                {
                    dp[i][j][k]=(dp[i][j-1][k-1]*(m-j+1)*i)/(n*m-k+1)+(dp[i-1][j][k-1]*(n-i+1)*j)/(n*m-k+1)+
                    (dp[i-1][j-1][k-1]*(m-j+1)*(n-i+1))/(n*m-k+1);
                }
                else{
                    dp[i][j][k]=(dp[i][j-1][k-1]*(m-j+1)*i)/(n*m-k+1)+(dp[i-1][j][k-1]*(n-i+1)*j)/(n*m-k+1)+
                    (dp[i-1][j-1][k-1]*(m-j+1)*(n-i+1))/(n*m-k+1)+(dp[i][j][k-1]*(j*i-(k-1)))/(n*m-k+1);
                }
            }
        }
    }
    double sum=0;
    for(int i=1;i<=n*m;i++)//算期望值
    {
        sum+=dp[n][m][i]*i;
    }
    printf("%.12lf\n",sum);
}
int main()
{
    int t;
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d%d",&n,&m);
        solve();
    } 
}