HDU 4711 Weather：對數概率 DP + 字典序最小路徑重構

HDU 4711 Weather：對數概率 DP + 字典序最小路徑重構

題目大意：某人在 m 個地點停留 n 天，每天觀測到一種天氣（w 種）。給出：地點間轉移概率、地點-天氣發射概率、n 天觀測天氣序列。求最可能的地點序列（最大後驗概率），若多解輸出字典序最小者。

核心難點：概率下溢與精度

n ≤ 2000，連乘 2000 個 <1 概率會導致 double 下溢為 0，long double 亦不可靠。
解法：取對數轉加法。
log(P₁×P₂×...×Pₙ) = log P₁ + log P₂ + ... + log Pₙ。
最大化概率 ⇔ 最大化對數概率和。
零概率處理：log(0) = -INF（代碼用 -1e7）。

DP 定義與轉移

dp[i][j] = 前 i 天、第 i 天在 j 地點的最大對數概率。
dp[i][j] = max_k { dp[i-1][k] + log(trans[k][j]) + log(emit[j][weather[i]]) }。
記錄 fa[i][j] = 使 dp 取最大值的前驅地點 k，用於路徑回溯。
字典序最小：轉移時若值相等，取 k 較小者（或回溯時從小到大檢查）。

代碼關鍵點（C++）

• 輸入讀取：n,m,w，天氣序列 obs[1..n]，轉移矩陣 trans[m][m]，發射矩陣 emit[m][w]。
• 預處理對數：if (x==0) logx = -INF; else logx = log(x);。
• DP 初始化：dp[0][0]=0, 其他=-INF（假設第 0 天在位置 0）。
• 三層循環：天數 → 當前地點 → 前驅地點。
• 回溯：從 dp[n][*] 最大值位置遞歸輸出路徑。

調試心得

作者踩坑點：
1. long double 仍 WA → 必須用對數。
2. eps=1e-16 判零失敗 → 直接 if (x == 0.0) 判零才 AC。
3. 字典序處理需在 DP 轉移或回溯中顯式保證。

總結

HMM (隱馬爾可夫模型) 維特比算法標準應用。對數域計算 是避免下溢的關鍵工程技巧。路徑重構記錄前驅，字典序最小需額外比較。模板化程度高，值得收藏作為 HMM 參考實現。