ZOJ Problem Set - 3822Domination(DP)

题目大意：

给你一个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 
      
       #include 
       
        #include 
        
         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;}