最終的に食べる林檎の集合を考えます。 食べた林檎の集合をいくつかの連続区間の和として表してみます。 このとき、区間同士は共通部分を持たないようにとります。 このとき、各区間の長さは \(K\) 以上です。 そして逆に、各区間の長さが \(K\) 以上になるように交差しない区間を取れば、ちょうどそれだけのりんごを食べるような操作が作れます。

あとは DP でできます。 \(dp[i]=\)先頭 \(i\) 番目だけを考えたときの答えとします。 遷移は以下の \(2\) 種類があります。

• \(dp[i]=\max(dp[i],dp[i-1])\): 林檎 \(i\) を取らないことに対応する遷移
• \(dp[i]=\max(dp[i],dp[j]+A_{j+1}+\cdots+A_i)\): 連続区間として \([j+1,i]\) をとる遷移

\(2\) 番目の遷移が重いです。 そこで、\(dp2[i]=\max(dp[i],dp2[i-1]+A_i)\) とすると、\(2\) 番目の遷移が \(dp[i]=max(dp[i],dp2[i-K]+A_{i-K+1}+\cdots+A_i)\) となり、\(O(1)\) で処理できるようになります。 これで、全体で \(O(N)\) 時間でこの問題は解けました。

実装例