HDU 4405 Aeroplane Chess：概率 DP 計算期望擲骰次數

問題描述

棋盤 0 到 n 共 n+1 格。從 0 起，每回合擲均勻六面骰（1~6），前進對應步數。部分格子有傳送門 a -> b（單向），落在 a 立即傳送至 b（不消耗骰子）。求從 0 到達 n 的期望擲骰次數。

DP 狀態與轉移

• dp[i]：從格子 i 到達 n 的期望擲骰次數。
• 終點 dp[n] = 0。
• 若 i 有傳送門 line[i] = j，則 dp[i] = dp[j]（強制傳送）。
• 否則：dp[i] = 1 + (1/6) * Σ_{k=1..6} dp[i+k]（i+k > n 視為 n 或忽略，題目保證可達）。
• 從 n-1 遞推到 0。

代碼實現

#include 
#include 
#include 
using namespace std;
const int maxn = 100000;
double dp[maxn];
int line[maxn];

int main() {
    int n, m;
    while (scanf("%d%d", &n, &m) && n+m) {
        memset(line, -1, sizeof(line));
        memset(dp, 0, sizeof(dp));
        for (int i = 1; i <= m; i++) {
            int a, b; scanf("%d%d", &a, &b);
            line[a] = b;
        }
        for (int i = n-1; i >= 0; i--) {
            if (line[i] != -1) { dp[i] = dp[line[i]]; continue; }
            for (int k = i+1; k <= i+6; k++)
                dp[i] += (1.0/6.0) * dp[k];
            dp[i] += 1;
        }
        printf("%.4lf\n", dp[0]);
    }
    return 0;
}

關鍵點

• 傳送門處理：落地即傳送，不再擲骰，故 dp[i] = dp[to]。
• 期望線性：E = 1 + 平均(E_next)。
• 逆序 DP 保證依賴已計算。
• 輸出保留 4 位小數。