Dec 18, 2016 修文: 此篇算法是錯的, 底下性質二的證明不正確.
認真回一篇好了.
這題只需要一次 BFS 計算每個位置下列兩個值即可. 令 d(v) 為起點至該點圖上的距離.
當說到 "在某位置停留" 時指的是在該位置重複獲利 (即使用了 self-loop).
一. 不在任何位置停留下起點到該點 v 走過 d(v) 步最佳獲利
二. 從起點到該點經過 N 天 (N 為題目所給天數) 最佳獲利
值一可簡單 DP 完成, 或是一併在計算值 (2) 之 BFS 時計算.
值二不難看出等價於
二'. 從起點不在任何位置停留, 經過 d(v) 步抵達該點 v 後停留至 N 天之最佳獲利
(我們只需證明以下性質: 最佳獲利途徑必為起點 d(v) 步直達終點後停留原地獲利.
性質一. 最佳路徑上終點必有最大獲利.
證明. 假設不然, 則路徑上有一位置 w 獲利為最大(必然大過終點).
則由起點出發延最佳路徑抵達 w 後停留至 N 天必獲利更多, 矛盾. ▓
性質二. 最佳路徑必為圖上從起點至終點最短路徑, 不經停留, 留在終點獲利.
證明. 由性質一可知越早抵達終點越佳; 若最佳路徑不為最短路徑, 則使用最短路徑抵達
終點後停留必可獲利更多, 矛盾.
Dec 18, 2016 修文: 此證明忽略了最短路徑上獲利可能很低, 因此是錯誤的.
)
值二'利用值一常數時間即可計算.
此圖每個位置只有最多八個鄰居, 所有位置值一可在線性時間計算完成.
(事實上最短路徑方向的關係, 只有最多三個鄰居有影響.)
而執行 BFS N 步後 (若所要求天數少 BFS 深度可提早終止), 將值二最大的位置與值輸
出即可. 連路徑都需要的話在 DP 時記錄前一個位置即可.
整個演算法可在線性時間完成.
不難看出這個演算法可推廣到任意圖, 而執行時間仍然為線性.
(當然, 這時圖的邊數也會被算在內.)