ZOJ 3822 Domination(概率dp)

一个n行m列的棋盘，每天可以放一个棋子，问要使得棋盘的每行每列都至少有一个棋子 需要的放棋子天数的期望。

dp[i][j][k]表示用了k天棋子共能占领棋盘的i行j列的概率。

他的放置策略是，每放一次，就会有四种可能

1）增加一行一列

2）增加一行

3)增加一列

4）不变

所以他放置的概率就可以求出来，每次放下的概率就是当前能放的点除以总的空的点数。

最后统计期望的时候需要统计在第k天刚好符合占满n行m列的概率，就是dp[i][j][k]-dp[i][j][k-1]

#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn = ;
double dp[maxn][maxn][maxn*maxn];int main()
{
    int T;
    scanf("%d", &T);
    while (T--)
    {
        int n, m;
        scanf("%d %d", &n, &m);
        int sum = n * m;
        for (int i = ; i <= n; i++)
            for (int j = ; j <= m; j++)
                for (int k = ; k <= sum; k++)
                    dp[i][j][k] = ;
        dp[][][] = 1.0;
        for (int k = ; k <= sum; k++)
        {
            for (int i = ; i <= n; i++)
            {
                for (int j = ; j <= m; j++)
                {
                    dp[i][j][k] += dp[i][j][k - ] * ((i * j - k + ) * 1.0 / (sum - k + ));//新添加的位置没有新增加行和列,所以他的概率就是(还剩下多少个符合不增加行和列能填的格子)/总的能填的格子
                    dp[i][j][k] += dp[i - ][j][k - ] * ((n - i + ) * j * 1.0 / (sum - k + ));//同理增加行不增加列
                    dp[i][j][k] += dp[i][j - ][k - ] * (i * (m - j + ) * 1.0 / (sum - k + ));//增加列不增加行
                    dp[i][j][k] += dp[i - ][j - ][k - ] * ((n - i + ) * (m - j + ) * 1.0 / (sum - k + ));//增加行和列
                }
            }
        }
        double ans = ;
        for (int k = ; k <= sum; k++)
            ans += (dp[n][m][k] - dp[n][m][k - ]) * k;//第k天刚好填满n和m所以就是dp[n][m][k] - dp[n][m][k - 1]
        printf("%.10f\n", ans);    }    return ;
}