Overview

This problem asks us to trim \(N\) flowers lined up in a row to maximize the sum of their final heights, subject to the condition that the difference between the maximum and minimum heights of any consecutive \(K\) flowers is at most \(D\).

Analysis

The condition “the difference between the maximum and minimum heights of any consecutive \(K\) flowers is at most \(D\)” is equivalent to “the difference in height between any two flowers at a distance of at most \(K-1\) is at most \(D\)”.

The height of each flower cannot exceed its original height \(H_i\). Therefore, we consider determining the upper bound for the height of each flower. Initially, we set the upper bound of the height of each flower \(i\) to \(dp[i] = H_i\).

For two flowers \(i\) and \(j\) at a distance of at most \(K-1\), if the difference between \(dp[i]\) and \(dp[j]\) exceeds \(D\), we need to adjust and lower the higher upper bound. Specifically, the lower upper bound plus \(D\) becomes a candidate for the higher upper bound.

To perform this adjustment for all flowers, a single pass in one direction (for example, from left to right) is insufficient. This is because a lower flower on the right can also lower the upper bound of a flower on the left. Therefore, we perform two scans in total: one pass from left to right, and another pass from right to left.

For example, when scanning from left to right, the upper bound of flower \(i\)’s height is updated under the condition that it cannot exceed the minimum of the \(dp\) values of the flowers within the left \(K-1\) range plus \(D\). That is, we update \(dp[i] = \min(dp[i], \min(dp[i-K+1], \dots, dp[i-1]) + D)\). We update from right to left in a similar manner.

By performing these two passes, we can find the upper bounds where the differences in height between all flowers within a distance of \(K-1\) from each other are at most \(D\). The sum of these upper bounds will be the maximum total height we can achieve without trimming more than necessary.

Algorithm

To efficiently find the minimum of the last \(K-1\) \(dp\) values during the left-to-right and right-to-left scans, we use the Sliding Window Minimum algorithm.

The Sliding Window Minimum is implemented using a double-ended queue (deque). - The queue stores the indices of the elements. - The front of the queue always holds the index of the minimum value in the current window. - When adding a new element, if the \(dp\) value of the element at the back of the queue is greater than or equal to the \(dp\) value of the new element, we remove them from the queue (to maintain monotonic increasing order). - If the index at the front of the queue falls out of the window (i.e., its distance exceeds \(K-1\)), we remove it.

This allows us to retrieve the minimum value of the window in \(O(1)\) time during each scan, processing the entire array in \(O(N)\) time.

Complexity

• Time Complexity: \(O(N)\) Each element is added to and removed from the deque at most once, resulting in an overall time complexity of \(O(N)\).
• Space Complexity: \(O(N)\) Proportional to the size of the \(dp\) array and the deque.

Key Implementation Points

• When \(K = 1\), the condition becomes “any consecutive 1 flower,” where the maximum and minimum are the same, so the difference is always 0, which satisfies being at most \(D\). Therefore, we can output the sum of the original heights without any trimming.

• In the left-to-right scan, at index \(i\), we exclude elements with indices less than \(i - (K-1)\) from the queue. In the right-to-left scan, at index \(i\), we exclude elements with indices greater than \(i + (K-1)\) from the queue.

• The update of \(dp[i]\) is done by taking the minimum of the original upper bound \(H_i\) and the minimum value \(+ D\) (i.e., dp[i] = min(dp[i], dp[dq.front()] + D)).

  Source Code

#include <iostream>
#include <vector>
#include <deque>
#include <algorithm>

using namespace std;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, K;
    long long D;
    cin >> N >> K >> D;
    
    vector<long long> H(N);
    for (int i = 0; i < N; ++i) {
        cin >> H[i];
    }
    
    if (K == 1) {
        long long ans = 0;
        for (int i = 0; i < N; ++i) {
            ans += H[i];
        }
        cout << ans << "\n";
        return 0;
    }
    
    int L = K - 1;
    vector<long long> dp(N);
    for (int i = 0; i < N; ++i) {
        dp[i] = H[i];
    }
    
    // Left to right pass
    deque<int> dq;
    for (int i = 0; i < N; ++i) {
        if (!dq.empty()) {
            dp[i] = min(dp[i], dp[dq.front()] + D);
        }
        while (!dq.empty() && dp[dq.back()] >= dp[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        while (!dq.empty() && dq.front() <= i - L) {
            dq.pop_front();
        }
    }
    
    // Right to left pass
    dq.clear();
    for (int i = N - 1; i >= 0; --i) {
        if (!dq.empty()) {
            dp[i] = min(dp[i], dp[dq.front()] + D);
        }
        while (!dq.empty() && dp[dq.back()] >= dp[i]) {
            dq.pop_back();
        }
        dq.push_back(i);
        while (!dq.empty() && dq.front() >= i + L) {
            dq.pop_front();
        }
    }
    
    long long ans = 0;
    for (int i = 0; i < N; ++i) {
        ans += dp[i];
    }
    
    cout << ans << "\n";
    
    return 0;
}

This editorial was generated by or-glm5.2-high.