ACdream 1113 The Arrow：骰子期望 DP 解法詳解

問題背景

Kuangbin 想透過擲骰子決定是否成為「中國的綠箭俠」。規則如下：先寫下一個正整數 N，然後反覆擲一顆標準六面骰子（點數 1~6 機率均等）。若目前累計點數加上本次擲出的點數不超過 N，則累加；否則本次擲骰不算，累計點數不變。當累計點數恰好等於 N 時停止。求期望擲骰次數。

核心思路：動態規劃求期望

定義 dp[i] 為當前累計點數為 i 時，仍需擲骰的期望次數。顯然 dp[N] = 0。對於 i < N，考慮下一步擲出 j (1≤j≤6)：

• 若 i + j > N，狀態不變，仍停留在 i，發生機率 1/6。
• 若 i + j ≤ N，轉移至 i+j，期望變為 dp[i+j]，機率 1/6。

列出方程：

dp[i] = (cnt/6) * dp[i] + (1/6) * Σ dp[i+j] + 1

其中 cnt 為導致超過 N 的點數個數（即 i+j > N 的 j 數量）。移項整理得：

dp[i] = (6 + Σ dp[i+j]) / (6 - cnt)

從 i = N-1 遞推至 0 即可得到答案 dp[0]。

算法複雜度

狀態數 O(N)，每狀態轉移 O(6)，總時間 O(N)，空間 O(N)。N ≤ 100,000，極其高效。

參考代碼 (C++)

#include <cstdio>
#include <cstring>
const int MAXN = 100005;
double dp[MAXN];

int main() {
    int T, n;
    scanf("%d", &T);
    while (T--) {
        scanf("%d", &n);
        memset(dp, 0, sizeof(dp));
        dp[n] = 0.0;
        for (int i = n - 1; i >= 0; --i) {
            dp[i] = 0;
            int cnt = 0;
            for (int j = 1; j <= 6; ++j) {
                if (i + j > n) ++cnt;
                else dp[i] += dp[i + j];
            }
            dp[i] += 6;
            dp[i] /= (6 - cnt);
        }
        printf("%.2f\n", dp[0]);
    }
    return 0;
}

關鍵點總結

• 期望 DP 的典型「自迴路」處理：將留在原狀態的機率移至左邊。
• 逆序推導避免循環依賴。
• 雙精度 double 足夠滿足保留兩位小數的精度要求。