f314. 3. 勇者修煉 -- 2020年10月APCS | From: [36.225.24.5] | 發表日期 : 2023-10-10 01:34

完整題解：https://moon-jam.me/zerojudge_f314/

 

解題思路：  

這題比較困難的地方是每一步是可以往左也可以往右的，我的解決方法是一樣使用DP，每層計算時先從左邊往右跑一次，再從右邊往左跑一次，最後取兩個方向中比較大的當作那個點的值，可以這樣做是因為在每一層中到達一個點一定是在該層移動時，方向必定不變(也就是說左邊來的就會是一路向左，從右邊來的就會是一路向右)，因此只要個別比較這兩種狀況就能解決了。

詳細的狀態轉移式可以見程式碼中的註解。

 

🌟 因為每次在比較兩個方向時都是在比較同一層的，所以可以就單純開一個一為陣列紀錄，但兩個方向的值一定要在最後都跑完之後再比較，假設事先計算由左往右再計算由右往左，如果在右往左時每算完一個數就比跟左往右的比較一次，那當計算新的點時其右邊的最大經驗就可能會是從左邊加過去的，那目前這格的數字就會被重複計算。