LightOJ 1030 Discovering Gold：洞穴期望黃金 DP

題目描述

1×N 洞穴，起點 1，終點 N。每回合擲 6 面骰子，前進 X 格（超過 N 重擲），收集該格黃金。到達 N 停止。求期望總黃金。N ≤ 100。

DP 遞推

E[i]：從第 i 格開始的期望黃金（含當前格）。
E[N] = gold[N]。
對 i < N：E[i] = gold[i] + (1/k) * Σ_{j=1..k} E[i+j]，其中 k = min(6, N-i)（超出 N 的骰面重擲，等價於只考慮有效步數並均分概率）。

C++ 代碼實現

#include <bits/stdc++.h>
using namespace std;

double E[105], gold[105];

int main() {
    int T; scanf("%d", &T);
    for (int cs=1; cs<=T; ++cs) {
        int N; scanf("%d", &N);
        for (int i=1; i<=N; ++i) scanf("%lf", &gold[i]);
        E[N] = gold[N];
        for (int i=N-1; i>=1; --i) {
            int k = min(6, N-i);
            double sum = 0;
            for (int j=1; j<=k; ++j) sum += E[i+j];
            E[i] = gold[i] + sum / k;
        }
        printf("Case %d: %.6f\n", cs, E[1]);
    }
    return 0;
}

關鍵點

• 重擲骰子等價於條件概率：只在有效步數中均勻分布。
• 逆序 DP 從 N-1 遞推到 1。
• 雙精度輸出 %.6f 滿足精度要求。