(zoj3822)Domination

发表于 | 分类于 ，

原题链接

思路:

概率dp

以$d(i,j,k)$表示已摆放$i$个棋子, 这$i$个棋子占据$j$行$k$列的概率.

则有如下转移方程:

当$j=n \land k=m$时去掉第一项(意味着填满后不继续放棋子)

边界条件为$d(1,1,1)=1$, 答案为$\sum_{i=1}^{nm} i \times d(i,n,m)$

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <cstring>
#include <utility>
using namespace std;
const int Mn(55),Mx(5050);
double dp[Mx][Mn][Mn];

int main() {
    int T;
    scanf("%d",&T);
    while(T--) {
        int n,m;
        scanf("%d %d",&n,&m);
        if(n>m) {
            swap(n, m);
        }
        //初始化
        memset(dp,0,sizeof dp);
        dp[1][1][1] = 1;
        //递推
        for(int i(2);i<=m*n;++i) {
            for(int j(1);j<=n;++j) {
                for(int k(1);k<=m;++k) {
                    if(j<n||k<m) {
                        dp[i][j][k] += dp[i - 1][j][k] * (j * k - i + 1) / (double) (n * m - i + 1);
                    }
                    dp[i][j][k] += dp[i-1][j-1][k]*((n-j+1)*k)/(double)(n*m-i+1);
                    dp[i][j][k] += dp[i-1][j][k-1]*(j*(m-k+1))/(double)(n*m-i+1);
                    dp[i][j][k] += dp[i-1][j-1][k-1]*((n-j+1)*(m-k+1))/(double)(n*m-i+1);
                }
            }
        }
        //计算答案
        double ans(0);
        for(int i(1);i<=m*n;++i) {
            ans += dp[i][n][m]*i;
        }
        printf("%.8f\n",ans);
    }
    return 0;
}