操作を \(0\) 回以上繰り返して得られるブロックの列は\(N\) 個のブロックのうちいくつかの連続する \(K\) の倍数個のブロックを消した列です。

よって、以下のような動的計画法が有効です。

\(\text{dp}[i]=\) 左から \(i\) 番目のブロックまでの列で同じ問題を解いたときのブロックに書かれた数の合計の最大値

とします。このとき、最後の右の \(i\) 番目のブロックが残っているか残っていないかの二択で、残っていない場合は \(i-K+1\) から \(i\) 番目までのブロックが残っていないことになります。したがって、遷移は以下のようになります。

\(\text{dp}[i]=\max(dp[i-K],dp[i-1]+a[i])\)

もちろん、\(i<K\) のときはかならず\(\text{dp}[i]\) では \(i\) 番目のブロックを残すので、\(\max\) の左側の項は考慮されません。

したがって、全体で時間計算量 \(\mathrm{O}(N)\) で解くことができます。

実装例(C++)

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, k;
    cin >> n >> k;
    vector<int> a(n);
    for (auto& e : a) cin >> e;
    vector<long long> dp(n + 1, -1e18);
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        dp[i + 1] = dp[i] + a[i];
        if (i + 1 >= k) dp[i + 1] = max(dp[i + 1], dp[i + 1 - k]);
    }
    cout << dp[n] << endl;
}