クッキーをお菓子 \(0\) とし、ケーキをお菓子 \(1\) とします。
サイクルについて寄与の最大値を求める際、 \(dp[i][j][k] :=\) サイクルの \(i\) 人目までのお菓子を決め打ち、 \(1\) 人目はお菓子 \(k\) を、 \(i\) 人目はお菓子 \(j\) をあげる際の \(2\) 人目から \(i\) 人目までのうれしさの合計の最大値とする DP を用いて \(O(N)\) で解くこともできます。