ZOJ Monthly, July 2012 - G : Treasure Hunt III

問題概要

n(<10^5)個の部屋が環状に並んでいる。最初は部屋Sにいる。これから最大T回部屋を移動して各部屋にある価値v[i]の宝を集めたい。ただし、ある部屋の宝をとるとその両隣の部屋の宝が消える。

解法

最適ルートは、右→左か左→右なので、今いる位置から右に進んだ場合と左に進んだ場合でそれぞれDPして最適解を求めておき、最後にその2つをマージするようにすればよい。うまく実装する自信がなかったので、初期位置をとる場合ととらない場合で場合分けした。場合分けも2種類くらいならまあ。