この問題は DP により解くことができます。

\(\mathrm{DP}[i]\) を「最後に収穫した木が \(i\) であるときの、収穫量の最大値」とします。このとき、

\(\mathrm{DP}[i] = A_i + \max_{1\leq j < i-K}\mathrm{DP}[j]\)

となります。空集合に対する \(\max\) を \(0\) と定めれば、これは \(i \leq K\) でも成立します。

この DP の遷移を計算するとき、 \(i\) の増加に伴って \(\max\) を取る対象は単調に増加します。よって、この値も同時に管理・更新することで、遷移を \(O(1)\) で行うことができ、全体で \(O(N)\) 時間でこの問題を解くことができます。

数式で表現すれば、\(\mathrm{DP'}[i]=\max_{1 \leq j < i}\mathrm{DP}[j]\) と置いて

• \(\mathrm{DP}[i] = A_i + \mathrm{DP'}[i-K]\)
• \(\mathrm{DP'}[i] = \max(\mathrm{DP'[i-1], DP[i-1]})\)

とするDPと思うこともできます。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

int main(){
  int n, k;
  cin >> n >> k;
  vector<int>a(n+1);  // 1-indexed
  for(int i=1; i<=n; i++) cin >> a[i];

  vector<long long>dp(n+1, -1e18);
  dp[0] = 0;
  long long M = 0;  // M = max(dp[0], ..., dp[i-K])

  for(int i=1; i<=n; i++){
    dp[i] = M + a[i];
    M = max(M, dp[max(0, i-k)]);
  }

  cout << *max_element(dp.begin(), dp.end()) << endl;
}

実装例 (Python)

N, K = map(int, input().split())
A = [-1] + list(map(int, input().split()))  # 1-indexed

dp = [-10**18] * (N+1)
dp[0] = 0
M = 0  # M = max(dp[:max(0, i-K)], default=0)

for i in range(1, N+1):
  dp[i] = M + A[i]
  M = max(M, dp[max(0, i-K)])

print(max(dp))