COLOCON -Colopl programming contest 2018-　D すぬけそだて――トレーニング――

問題概要

スタミナの上限が $X$ で、スタミナを全て消費する時間の候補が $N$ 個ある。
時刻 $0$ のときにスタミナが $X$ で、 $1$ 単位時間にスタミナが $1$ 回復するとき、 $i (1 <= i <= N )$ 回スタミナを消費する場合の消費したスタミナの合計の最大値を各 $i$ について求めよ。

制約
$1 \le N \le 5000$
$1 \le X \le 10^9$
$1 \le T_i \le 10^9$

TLE解法

dp[ $i$ ][ $j$ ]:= 最後に起動したのが $i$ 番目の候補で、今までに $j$ 回起動したときの消費したスタミナの最大値
とすると、遷移が $O(N)$ かかるので、計算量は合計で $O(N^3)$ になる。

Submission #2074687 - COLOCON -Colopl programming contest 2018-

解法

最大値を求めるDPは最大値になりうる遷移以外は無駄なので、必要な遷移のみを考えることによって高速化する。

スタミナを消費する回数がたくさんある場合、上限までスタミナが回復してからスタミナを消費すると、上限まで回復したあとから消費するまでにかかる時間ぶん、スタミナを無駄にしてしまう。
また、スタミナを消費する回数が少ない場合、上限まで回復するまで待った方が、上限まで回復する前にスタミナを消費するより、多くのスタミナを消費できる。
よって、スタミナを消費する回数によって、2通りの遷移が考えられ、