ZOJ Problem Set - 3822Domination(DP)

problemCode=3822">题目链接

题目大意：
给你一个n * m的棋盘，每天都在棋盘上面放一颗棋子。直到这个棋盘上的每行每列都有至少有一颗棋子。求要用的天数的期望。

解题思路：
        先求出不同摆法的棋盘的概率，然后在和天数相乘就是期望。

        我们将棋盘划分为四个部分：当中一部分为每行没列都至少有一个棋子。

        然后得出状态转移方程：
        dp[x][y][k]:表示x行y列已经满足要求，用了k个棋子。
        dp[x][y][k + 1] = dp[x][y][k] *(x *y - k)/ (m * n - k);
        dp[x][y][k + 1] = dp[x - 1][y][k] * (n - x + 1) * y / (n * m - k);
        dp[x][y][k + 1] = dp[x][y - 1][k] * (m - y + 1) *x / (n *m - k);
        dp[x][y][k + 1] = dp[x - 1][y - 1][k] *（m - y + 1) *(n - x + 1) / (n * m - k);
        dp[0][0][0] = 1;而且dp[n][m][k] -= dp[n][m][k - 1].由于这个时候已经按要求覆盖了整个棋盘。可是再下第k颗棋子的时候，是有前面的k - 1颗棋子的总数来决定的。可是到k - 1的时候事实上就是能够停止的，而之前这个种类已经加过了，所以减掉。

代码：

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;

const int maxn = 55;

double dp[maxn][maxn][maxn * maxn];

int main () {

    int T;

    int n, m;

    scanf ("%d", &T);

    while (T--) {

        dp[0][0][0] = 1;

        scanf ("%d%d", &n, &m);            

        for (int i = 1; i <= n; i++)

            for (int j = 1; j <= m; j++)

                for (int k = 0; k < i * j; k++) {

                    dp[i][j][k + 1] = 0;

                    dp[i][j][k + 1]    += dp[i][j][k] * (i * j - k) / (n * m - k);

                    //printf ("%.12lf\n", dp[i][j][k + 1]);

                    if (i)

                        dp[i][j][k + 1] += dp[i - 1][j][k] * (n - i + 1) * j/ (n * m - k);

                    if (j)

                        dp[i][j][k + 1] += dp[i][j - 1][k] * (i * (m - j + 1)) / (n * m - k);

                    if (i && j)

                        dp[i][j][k + 1] += dp[i - 1][j - 1][k] * (n - i + 1) * (m - j + 1) / (n * m - k);

                }

        double ans = max(n, m) * dp[n][m][max(n, m)];

        for (int k = max(n, m) + 1; k <= n * m; k++)

            ans += k * (dp[n][m][k] - dp[n][m][k - 1]);

        printf ("%.12lf\n", ans);

    }

    return 0;

}