The Last Puzzle (ZOJ Problem Set - 3541)

ZOJ Online Judge

http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3541

問題

ボタンがn個直線上に並んでいる。各ボタンは押してからTi秒後に元に戻ってしまう。全てのボタンを押した状態にするにはどの順番で押せばよい？
1<=n<=200
1<=Ti<=1000000

解法

左右の端を持ったDP。dp[lr][l][r]は左からlまでと右からrまで押して最後に押したのがlr(=0 or 1)の状態で残りのボタンを押すのにかかる最短時間を表す。O(n^2)で解ける。