E - Work or Rest Editorial by Cyanmond


DP の定義を公式解説と変えます。こちらの方がイメージしやすい人もいる気がします。

まずは公式解説の通りに \(B\) を定義し、計算します。

\(\mathrm{dp}_i\)\(i\) 日目は休むとしたとき \(i\) 日目までの生産量として考えられる最大値と定義します。

\(i \geq 2\) であれば、 \(\displaystyle \mathrm{dp}_i = \max_{j=1}^{i-1} (\mathrm{dp}_j + B_{i-j-1})\) です。

\(\mathrm{dp}_1 = 0\) と初期化し、 \(i = 2, 3, \cdots , N+1\) の順に式の通りに計算していけば、計算量 \(O(N^2)\) で DP テーブルが埋まります。問題の答えは \(\mathrm{dp}_{N+1}\) です。

posted:
last update: