一個很重要的 observation: 在 optimal case中, Hermes 每次移動都只會行一段直線 (即唔會行 x 再行 y )
由於傳完 message 去第 i 個點後, Hermes 的位置只有大約 4000 個可能性 (或2N), 所以諗到用 dp 做, transfer 時, 因為由上面的 observation, 所以可以 O(1) 完成每個 state 的 transfer, 總時間上限 O(N2)
由於傳完 message 去第 i 個點後, Hermes 的位置只有大約 4000 個可能性 (或2N), 所以諗到用 dp 做, transfer 時, 因為由上面的 observation, 所以可以 O(1) 完成每個 state 的 transfer, 總時間上限 O(N2)
No comments:
Post a Comment