UVALive 6972-Domination【概率DP】

秒速五厘米 2023-06-03 12:59 14阅读 0赞

题意：给你一个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;
    }