Grazing on the Run　(PKU 3042)

PKU Online Judge

http://acm.pku.edu.cn/JudgeOnline/problem?id=3042

問題

直線上に牧草がN個ある。それぞれの牧草を食べるまでの時間の和を最小化したい。自分の初期位置がLの時、最小値はいくらか？
1<=N<=1000
1<=L<=1000000

解法

メモ化再帰で解く。
calc(dir, left, right)は左側はleftまで、右側はrightまでの牧草を食べ、最後に食べた牧草はdirの方向である場合、これから残りの牧草を食べるまでに掛かる時間の和の最小値を返す関数。
計算時間O(N^2)で解ける。