LightOJ 1317 - 期望球數：DP 計算 K 輪後籃子中球的期望數

問題建模

N 人，M 個籃子，K 輪。每輪每人獨立以概率 P 投中隨機一個籃子（衝突不影響概率）。求 K 輪後籃子中球的期望總數。

關鍵觀察

籃子身份不重要，只關心「每輪投中幾球」。設單輪投中球數為隨機變量 X ~ Binomial(N, P)。K 輪總球數 S = X₁ + ... + Xₖ，期望 E[S] = K · E[X] = K · N · P。

但題目要求 DP 過程（可能為教學目的），實際可直接用公式。此處給出 DP 解法。

DP 定義

dp[i][j]：前 i 輪總共投中 j 球的概率。

• dp[0][0] = 1
• 轉移：dp[i][j+l] += dp[i-1][j] * Pr(X=l)，l = 0..N

預計算二項分布

C[n][k] 組合數
Pr(l) = C(N, l) * P^l * (1-P)^(N-l)

期望計算

E = Σ j * dp[K][j]

完整代碼

#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;

double dp[110][1700];
double prob[20];
int C[20][20];

void initComb() {
    for (int i=0; i<=16; ++i) {
        C[i][0] = C[i][i] = 1;
        for (int j=1; j 0)
                    for (int l=0; l<=N; ++l)
                        dp[i][j+l] += dp[i-1][j] * prob[l];
        double E = 0;
        for (int j=0; j<=K*N; ++j) E += j * dp[K][j];
        printf("Case %d: %.12f\n", tc, E);
    }
    return 0;
}

複雜度

• 時間：O(K·N²) ≈ 100·16² = 25600
• 空間：O(K·N·K) = O(K²N) ≈ 2.5e5

備註

實際比賽中直接用 E = K * N * P 即可 AC，DP 為過度設計但有助於理解分布演化。