No.032 C

時刻 $t$ におけるそれ以降受けられる仕事の最大数を $C(t)$, それ以降受けられる仕事が最大のときの, $t$ 以降で最初に受ける仕事を $W(t)$ とする.

$t$ が開始時刻の仕事がなければ, $C(t) = C(t+1), W(t) = W(t+1)$ である.

$t$ が開始時刻の仕事があり, それを $i$ とすると:

• $C(t+1) = C(b_i)$ のとき: 無条件でその仕事を受ける.
• $C(t+1) \gt C(b_i) + 1$ のとき: 無条件でその仕事は受けない.
• $C(t+1) = C(b_i) + 1$ のとき: 仕事を受けても受けなくてもできる仕事量は変わらない. しかし辞書順最小の条件があるので, $i \lt W(t+1)$ ならば受けることになる. そうでなければ受けない.

仕事を受ける場合は $C(t) = C(t+1) + 1, W(t) = i$, 受けない場合は $C(t) = C(t+1), W(t) = W(t+1)$ となる.

これを順に計算していき, $C(0)$ が受けることができる最大の仕事量である.

受ける仕事の一覧は, $W_0 = W(0), W_1 = W(b_{W_0}), W_2 = W(b_{W_1})$ と拾っていく.