問題描述

N 條路（N≤100），初始戰力 f（≤10000）。每天隨機選一條路（概率 1/N）。第 i 條路難度 c_i：

• 若 f > c_i：花費 t_i = floor(φ·c_i²) 天逃脫（φ=(1+√5)/2）。
• 否則：花費 1 天，戰力增加 c_i，繼續。

求逃脫期望天數。多測試用例。

DP 定義

E(f)：當前戰力為 f 時的期望剩餘天數。
遞推：

E(f) = (1/N) * Σ_{i=1..N} {
    f > c_i ? t_i : (1 + E(f + c_i))
}

記憶化搜索

• 狀態：f。最大戰力：初始 ≤10000，每次增加 ≤10000，最多增加 N 次？實際上 f 遞增，最終必超過所有 c_i，遞歸有界。
• 上界估計：最壞情況每次選最小 c_i，但期望步數有限。數組開 dp[20005] 足夠（題目保證答案 ≤ 1e9）。
• 遞歸深度：戰力單調遞增，無環，安全。

代碼實現

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

const int MAXF = 20005;
double dp[MAXF];
int c[105];
int n, f0;
const double phi = (1 + sqrt(5.0)) / 2;

double dfs(int f) {
    if (dp[f] > 0) return dp[f];
    double ans = 0;
    for (int i = 0; i < n; ++i) {
        if (f > c[i]) {
            int t = (int)(phi * c[i] * c[i]); // floor 隱含在轉換中
            ans += t * 1.0 / n;
        } else {
            ans += (1.0 + dfs(f + c[i])) / n;
        }
    }
    return dp[f] = ans;
}

int main() {
    while (~scanf("%d%d", &n, &f0)) {
        for (int i = 0; i < n; ++i) scanf("%d", &c[i]);
        memset(dp, 0, sizeof(dp));
        printf("%.3f\n", dfs(f0));
    }
    return 0;
}

關鍵細節

1. 期望公式推導：E = Σ p_i * (cost_i + E_next)，p_i = 1/N。
2. φ 計算：(1+sqrt(5))/2，用 double 精度足夠。
3. t_i 取整：(int)(phi * c[i] * c[i]) 等價於 floor。
4. 記憶化數組大小：f 最大約 f0 + Σ c_i ≤ 10000 + 100×10000 = 1e6？但題目保證答案 ≤ 1e9，實際測試 dp[20005] 足夠（或用 map）。為保險可用 unordered_map 或開大數組 dp[200005]。
5. 輸出精度：%.3f 保留三位小數。

複雜度

• 狀態數：戰力從 f0 遞增至 > max(c_i)，步長不定，但每狀態計算 O(N)，總時間可接受。
• 記憶化避免重複計算，實際測試極快。

總結

ZOJ 3640 是「概率 DP + 記憶化搜索」的典型應用。關鍵在於：

1. 建立期望遞推方程 E(f) = Σ p_i * (即時花費 + 後續期望)。
2. 識別狀態單調性（戰力只增不減），保證遞歸無環、有界。
3. 記憶化數組/哈希表存儲已計算狀態，避免指數級重複計算。
4. 精度控制：double 足夠，輸出 %.3f。

此模板適用於所有「狀態單向轉移、隨機選擇動作、求期望步數/代價」問題。