ZOJ 3640 Cain 的逃脫期望：記憶化搜索解概率 DP

題目大意

n 條路，第 i 條難度 c_i。初始戰力 f。
每天隨機選一條路：
- 若 f > c_i，花費 t_i = φ * c_i^2 天逃脫（φ = (1+√5)/2）。
- 否則花費 1 天，戰力增加 c_i。
求逃脫期望天數 E。

狀態定義與轉移

dp[f] = 當前戰力為 f 時的期望剩餘天數。
dp[f] = (1/n) * Σ { t_i (if f > c_i) 1 + dp[f+c_i] (otherwise) }

遞歸邊界：戰力足夠大時直接逃脫。
戰力單調遞增，狀態有限（f ≤ 10000 + 100*10000 但實際可達狀態少），記憶化搜索即可。

C++ 參考代碼

const int MAXF = 200000;  // 足夠大的上界
int n, f0;
int c[105];
double dp[MAXF];
bool vis[MAXF];
const double phi = (1 + sqrt(5)) / 2;

double solve(int f) {
    if (f >= MAXF) return 0;  // 理論上不會達到，保護
    if (vis[f]) return dp[f];
    vis[f] = true;
    double res = 0;
    for (int i = 0; i < n; ++i) {
        if (f > c[i]) {
            int t = phi * c[i] * c[i];
            res += t;
        } else {
            res += 1 + solve(f + c[i]);
        }
    }
    dp[f] = res / n;
    return dp[f];
}

int main() {
    while (cin >> n >> f0) {
        for (int i = 0; i < n; ++i) cin >> c[i];
        memset(vis, 0, sizeof(vis));
        printf("%.3f\n", solve(f0));
    }
    return 0;
}

關鍵點

• 期望線性性質：E = 平均(各分支期望)。
• 狀態單調遞增無環，記憶化搜索不會無限遞歸。
• phi * c_i^2 需用 double 計算，最後輸出保留 3 位小數。
• 上界 MAXF 設為 200000 足夠（f ≤ 10000, c_i ≤ 10000, n ≤ 100，最壞 f + Σc_i ≤ 1e6，但期望收斂快，實際訪問狀態極少）。

避坑指南

1. 遞歸深度可能較大，建議改寫為迭代 DP（按 f 從大到小填表）或增大棧。
2. f > c_i 還是 f >= c_i？題目原文「larger than」即嚴格大於，代碼用 f > c[i]。
3. 多測試用例需清空 vis 數組。