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

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

問題描述

飛行棋 0..n 格。某些格有「飛機」可直接跳到目標格。從 0 開始，每回合擲均勻骰子（1-6），前進步數。超過 n 視為到達。求期望擲骰子次數。

DP 狀態與轉移

• 預處理 to[i]：從 i 經飛機跳轉後的最終位置（遞歸解析）
• dp[i]：從 i 到達終點的期望步數
• 邊界：dp[n] = dp[n+1] = ... = dp[n+5] = 0
• 逆序轉移（i 從 n-1 到 0）：
  若 to[i] != -1：dp[i] = dp[to[i]]（必經飛機）
  否則：dp[i] = 1 + (dp[i+1]+...+dp[i+6])/6

完整 AC 代碼

#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
const int N = 100010;
int n, m;
double dp[N];
int to[N];

double solve() {
    for (int i = 0; i < 6; i++) dp[n+i] = 0;
    for (int i = n-1; i >= 0; i--) {
        if (to[i] != -1) dp[i] = dp[to[i]];
        else {
            dp[i] = 1.0;
            for (int j = 1; j <= 6; j++) dp[i] += dp[i+j] / 6.0;
        }
    }
    return dp[0];
}

void input() {
    memset(to, -1, sizeof(to));
    while (m--) {
        int x, y; scanf("%d%d", &x, &y);
        to[x] = y;
    }
    for (int i = n-1; i >= 0; i--)
        if (to[i] != -1 && to[to[i]] != -1)
            to[i] = to[to[i]];
}

int main() {
    while (cin >> n >> m, n+m) {
        input();
        printf("%.4f\n", solve());
    }
    return 0;
}

關鍵點

1. 飛機鏈預處理：to[i] = to[to[i]] 遞歸展開
2. 逆序 DP 保證依賴已計算
3. 期望線性公式直接套用