您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> C++ 入門

ZOJ 3822 Domination 期望 DP 詳解 (2014 牡丹江區域賽 D 題)

編輯：C++ 入門

問題重述

N×M 棋盤，每天隨機空格放一子。求期望天數使每行每列至少一子。
1 ≤ N,M ≤ 50，多測試用例，精度 1e-8。

DP 狀態定義

dp[i][j][k] = 放 i 子後，佔 j 行 k 列的概率。
轉移：第 i+1 子落在：
1. 新行新列：(N-j)*(M-k) 格
2. 新行舊列：(N-j)*k 格
3. 舊行新列：j*(M-k) 格
4. 舊行舊列：j*k - i 格 (扣除已佔格)
分母均為 N*M - i (剩餘空格)。

期望計算公式

E = Σ i * dp[i][N][M] (i 從 1 到 N*M)

代碼實現 (滾動數組優化)

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
double dp[2][55][55]; // 滾動數組

int main() {
    int T, n, m;
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &n, &m);
        memset(dp, 0, sizeof(dp));
        dp[1][1][1] = 1.0; // 第一步
        int cur = 1, nxt = 0;
        int total = n * m;
        for (int i = 1; i < total; i++) {
            memset(dp[nxt], 0, sizeof(dp[nxt]));
            for (int j = 1; j <= n; j++) {
                for (int k = 1; k <= m; k++) {
                    if (dp[cur][j][k] == 0) continue;
                    if (j * k < i) continue; // 不合法
                    double denom = total - i;
                    if (j < n && k < m)
                        dp[nxt][j+1][k+1] += dp[cur][j][k] * (n-j)*(m-k) / denom;
                    if (j < n)
                        dp[nxt][j+1][k] += dp[cur][j][k] * (n-j)*k / denom;
                    if (k < m)
                        dp[nxt][j][k+1] += dp[cur][j][k] * j*(m-k) / denom;
                    if (j < n || k < m)
                        dp[nxt][j][k] += dp[cur][j][k] * (j*k - i) / denom;
                }
            }
            swap(cur, nxt);
        }
        double ans = 0;
        for (int i = 1; i <= total; i++) ans += i * dp[cur][n][m];
        printf("%.10f\n", ans);
    }
    return 0;
}