UVALive 6972-Domination【概率DP】

题意：给你一个n*m的方格，每天选择一个空格子放置棋子，使得棋盘每一行至少有一个，每一列也至少有一个，问你期望天数。

思路：f[i][r][c] 表示第i天已经有r行c列放置了棋子，然后考虑下一天会有哪种情况，

1. f[i + 1][r][c] : 在已经出现过的行列中 

2. f[i + 1][r + 1][c] : 在已经出现过的列中，但未出现的行中

3.f[i + 1][r][c + 1]: 在已经出现过的行中，但未出现的列中

4.f[i + 1][r + 1][c + 1] : 在未出现过的行列中

然后我们求出来概率，最后天数*概率相加就是期望。

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
#define mid ((l + r) >> 1)
const int maxn = 2510;
const int mod = 1e9 + 7;
double f[maxn][55][55];

int main()
{
    int t;
    scanf("%d", &t);
    while(t--)
    {
        int n, m;
        scanf("%d%d", &n, &m);
        for(int i = 0; i <= n * m; ++i)
            for(int j = 0; j <= n; ++j)
                for(int k = 0; k <= m; ++k)
                    f[i][j][k] = 0;
        f[0][0][0] = 1;
        for(int i = 0; i <= n * m; ++i)
        {
            for(int r = 0; r <= n; ++r)
            {
                for(int c = 0; c <= m; ++c)
                {
                    if((r == n && c == m) || f[i][r][c] == 0) continue;
                    double sum = n * m - i;
                    double p1 = (r * c - i) * 1.0 / sum;
                    double p2 = c * (n - r) * 1.0 / sum;
                    double p3 = r * (m - c) * 1.0 / sum;
                    double p4 = (n - r) * (m - c) * 1.0 / sum;
                    if(r * c > i) f[i + 1][r][c] += p1 * f[i][r][c];
                    if(r < n) f[i + 1][r + 1][c] += p2 * f[i][r][c];
                    if(c < m) f[i + 1][r][c + 1] += p3 * f[i][r][c];
                    if(r < n && c < m) f[i + 1][r + 1][c + 1] += p4 * f[i][r][c];
                }
            }
        }
        double ans = 0;
        for(int i = max(n, m); i <= n * m - min(n, m) + 1; ++i)
            ans += i * f[i][n][m];
        printf("%.12f\n", ans);
    }
    return 0;
}