ABC204 D Cooking
$ dp_{i, j}
:= 料理
$ i
まで見て(オーブンを区別すると考えて)
$ 1
つ目のオーブンでちょうど
$ j
分消費するようにできるか というDPを更新していく. すると,
$ j
を全探索することによって最短時間を求めることができる. 計算量は
$ O(N^2T_{max})
となり, これは十分高速である.
実装例:
https://atcoder.jp/contests/ABC204/submissions/23230263