Overview

This is a dynamic programming (DP) problem about harvesting fruits from trees arranged in a row, where you must maximize the harvest amount under the constraint that once you harvest from a tree, you cannot harvest from the next \(K\) trees.

Analysis

Key Observations

• If you harvest at tree \(i\), the next tree you can harvest from is tree \(i + K + 1\) or later
• Conversely, to harvest at tree \(i\), the previous harvest must have been at tree \(i - K - 1\) or earlier

Problem with the Naive Approach

Since there are 2 choices for each tree (“harvest” or “don’t harvest”), a brute force search would result in \(O(2^N)\) possibilities. This is far too slow for \(N \leq 2 \times 10^5\).

Solution Strategy

We use dynamic programming. Define \(dp[i]\) as “the maximum harvest amount when harvesting at tree \(i\)”. The state transition becomes:

\[dp[i] = A_i + \max(0, \max_{0 \leq j \leq i-K-1} dp[j])\]

However, if we search through all \(j\) for each \(i\), the complexity becomes \(O(N^2)\).

Key to Optimization

By separately maintaining \(max\_dp[i]\) as “the maximum value from \(dp[0]\) to \(dp[i]\)”, we can obtain \(\max_{0 \leq j \leq i-K-1} dp[j]\) as \(max\_dp[i-K-1]\) in \(O(1)\) time.

Algorithm

1. \(dp[i]\): Maximum harvest amount when harvesting at tree \(i\)
2. \(max\_dp[i]\): Maximum value among \(dp[0], dp[1], \ldots, dp[i]\)

State Transition: - When \(i \leq K\): There are no harvestable trees before tree \(i\), so \(dp[i] = A_i\) - When \(i > K\): \(dp[i] = A_i + max\_dp[i - K - 1]\) - Add \(A_i\) to the maximum value from harvesting at tree \(i - K - 1\) or earlier

Concrete Example (\(N = 5, K = 1, A = [3, 1, 4, 1, 5]\)):

\(i\)	\(A_i\)	\(dp[i]\)	\(max\_dp[i]\)	Explanation
0	3	3	3	First tree
1	1	1	3	Since \(K=1\), cannot reference previous tree
2	4	4 + 3 = 7	7	Uses \(max\_dp[0] = 3\)
3	1	1 + 3 = 4	7	Uses \(max\_dp[1] = 3\)
4	5	5 + 7 = 12	12	Uses \(max\_dp[2] = 7\)

The answer is \(max\_dp[4] = 12\) (harvesting from trees 0, 2, and 4)

Complexity

• Time Complexity: \(O(N)\) — constant time processing for each tree
• Space Complexity: \(O(N)\) — for the \(dp\) array and \(max\_dp\) array

Implementation Notes

• When \(i - K - 1 < 0\), there are no previously harvested trees (or no harvesting has been done), so \(dp[i] = A_i\)
• The final answer is \(max\_dp[N-1]\). This represents “the maximum value when the last harvest was at some tree”
• Pay attention to when to update \(max\_dp\): update \(max\_dp[i]\) after finalizing \(dp[i]\)

Source Code

def solve():
    N, K = map(int, input().split())
    A = list(map(int, input().split()))
    
    # dp[i] = maximum number of fruits that can be harvested when looking up to tree i
    # considering both cases: harvesting at tree i or not
    
    # dp[i] = maximum harvest amount up to that point when harvesting at tree i
    # To harvest at tree i, the last harvest must be at tree i-K-1 or earlier
    
    dp = [0] * N
    
    # max_dp[i] = maximum value from dp[0] to dp[i]
    # This allows us to get the maximum of dp[j] (j <= i-K-1) in O(1)
    
    for i in range(N):
        # When harvesting at tree i
        if i <= K:
            # i-K-1 < 0, so there are no trees harvested before this (or no harvesting done)
            dp[i] = A[i]
        else:
            # Maximum value when last harvest was at tree i-K-1 or earlier + A[i]
            # Or, when harvesting for the first time from no previous harvests, it's A[i]
            dp[i] = A[i]
    
    # max_dp[i] = max(dp[0], dp[1], ..., dp[i])
    max_dp = [0] * N
    max_dp[0] = dp[0]
    
    for i in range(1, N):
        # When harvesting at tree i, use the maximum value from harvesting at i-K-1 or earlier
        if i - K - 1 >= 0:
            dp[i] = max(dp[i], max_dp[i - K - 1] + A[i])
        
        max_dp[i] = max(max_dp[i - 1], dp[i])
    
    print(max_dp[N - 1])

solve()

---

This editorial was generated by claude4.5opus.