Acdream 1113 The Arrow：概率 DP 求期望骰子次數

題目大意

從位置 0 開始，每次擲均勻骰子（1~6），當前位 x，擲到 y。若 x+y > n 則停留在 x，否則移動到 x+y。求從 0 到達 n 的期望擲骰次數。

DP 定義與轉移

dp[i]：從位置 i 到達 n 的期望次數。dp[n] = 0。

從 i 出發，擲出 1..6：

• 若 i+j > n：留在 i，期望貢獻 dp[i]。
• 若 i+j ≤ n：移動到 i+j，期望貢獻 dp[i+j]。

每次擲骰計 1 次，列方程：

dp[i] = 1 + (Σ_{j: i+j≤n} dp[i+j] + Σ_{j: i+j>n} dp[i]) / 6

設 tot 為導致停留的點數個數（即 i+j > n 的 j 數），則：

dp[i] = 1 + (Σ dp[i+j] + tot * dp[i]) / 6
⇒ (6 - tot) * dp[i] = 6 + Σ dp[i+j]
⇒ dp[i] = (6 + Σ dp[i+j]) / (6 - tot)

代碼實現（C++）

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
double dp[MAXN];

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n; scanf("%d", &n);
        fill(dp, dp+n+1, 0);
        for (int i = n-1; i >= 0; --i) {
            int tot = 0; double sum = 0;
            for (int j = 1; j <= 6; ++j) {
                if (i + j > n) tot++;
                else sum += dp[i+j] / 6.0;
            }
            dp[i] = (1 + sum) * 6 / (6 - tot);   // 等價於 (6 + 6*sum) / (6-tot)
        }
        printf("%.2f\n", dp[0]);
    }
    return 0;
}

關鍵點

1. 逆序 DP：從 n-1 遞減到 0，保證依賴已計算。
2. 代數變形：將含 dp[i] 的方程解出來，避免迭代求解。
3. 精度：double 足夠，輸出保留兩位小數。

複雜度

• 時間：O(T * n)，n ≤ 1e5 極快。
• 空間：O(n)。