D - Cooking Editorial by kyopro_friends


オーブンを使う順序は関係なく、どの料理をどちらのオーブンで作るかのみが重要です。

\(2\) つのオーブンのどちらに割り当てるかによって料理を \(2\) つの集合に分けることを考えると、問題は「\(N\) 品の料理を \(2\) つの集合に分け、それぞれ作るのにかかる時間の合計の最大値を最小化せよ」と読み替えることが出来ます。

\(T_1+\ldots+T_N\)\(S\) とします。\(1\) つ目のオーブンを使う時間が \(2\) つ目のオーブンを使う時間以上であると仮定してよいです(そうでない場合、\(2\) つのオーブンを入れ替えれば良い)。このとき、\(1\) つ目のオーブンを使う時間は \(S/2\) 以上になります。この条件下で \(1\) つ目のオーブンを使う時間を最小化すればよいので、問題は「\(T_1,\ldots,T_N\) からいくつか選んだ和であって、\(S/2\) 以上の最小値は?」と読み替えることができます。

この問題は「\(T_1,\ldots,T_N\) からいくつか選んだ和を \(x\) にすることができるか?」という問題を各 \(x\) に対して答えることができれば解けます。これは部分和問題にほかならないので
\(dp[i][j]=T_1,\ldots,T_i\) からいくつか選んで和を \(j\) にできるか?
という真偽値を持つDPを用いて \(O(N \sum_i T_i)\) で求めることができます。

posted:
last update: