BZOJ 3029：守衛者的挑戰——期望 DP 與狀態壓縮

題目大意

n 個獨立事件，第 i 事件發生概率 pᵢ，收益 aᵢ（可負）。初始收益 k。求 n 事件後：發生事件數 ≥ l 且 總收益 ≥ 0 的概率。

DP 狀態設計

f[i][j][k]：前 i 個事件，已發生 j 個，當前收益為 k 的概率。

關鍵優化：收益維度壓縮

• 收益超過 n 後不可能扣成負數（最多剩 n 個事件，每次最少 -1）
• 將 k > n 統一映射到 n，k < -n 映射到 -n
• 第三維大小僅 2n+1，總狀態 O(n³)，n ≤ 200 可行

轉移方程

f[i+1][j+1][k + a[i+1]] += f[i][j][k] * p[i+1]   // 事件發生
f[i+1][j][k]             += f[i][j][k] * (1-p[i+1]) // 事件不發生

C++ 實現（關鍵結構）

struct Arr {
    double v[405]; // 映射 [-n, n] -> [0, 2n]
    double& operator[](int x) {
        if (x > n) x = n;
        if (x < -n) x = -n;
        return v[x + 200];
    }
} f[205][205];

最終答案

ans = Σ f[n][j][k]  (j ≥ l, k ≥ 0)

複雜度

• 時間：O(n³) ≈ 8×10⁶ 操作
• 空間：O(n³) 但常數小，通過內存限制