\(i\) 番目のニワトリを \(j\) 回選択したときの美味しさの最大値を \(d(i, j)\) とすると, 卵を産ませる回数が中途半端な場合は最適となりえず,

\[d(i, j) = \max \{ j A_i, (j-1) A_i + B_i, B_i \}\]

となる.

ここで, \(i_1\) 番目から \(i_2\) 番目のニワトリを \(j\) 回選択したときの美味しさの総和のグラフを考える. このグラフは絶対値の和のグラフと似たような形となり, 下に凸の形となる. よって, \(j\) は \(1\) に寄せるか \(M\) に寄せるかのどちらかの方が最適であるので, \(j\) は \(0, 1, M\) の 3 通りだけ考えればいい.

あとは DP を使う. \(i\) 番目のニワトリまで見たときに そのニワトリを \(j\) 回選択したときの最大の美味しさを \(D(i, j)\) とすると,

\[\begin{align} D(i, M) &= D(i-1, M) + d(i, M) \\ D(i, 1) &= \max \{ D(i-1, M), D(i-1, 1) \} + d(i, 1) \\ D(i, 0) &= \max \{ D(i-1, M), D(i-1, 1), D(i-1, 0) \} \end{align}\]

となり, これを順に更新していくｋ.