Space Elevator (UVa Live Archive Asia - 2008 Taipei(Taiwan))
問題
右方向にr個、左方向にq個止まる候補の箇所がある。各箇所はxiの場所にあり時間t1ｎそこに行くとmax(0, pi-t)の利益を1度だけ得る。利益の最大値を求めよ。
解法
dp[lr][left][right][t]でDPする。lrは左端、右端のどちらにいるか、leftは左側をどこまで行ったか、rightは右端、tは現在の時間を表す。これでDPするとメモリが足りないのでleftを使い回せば解ける。
