題目的難度顏色使用 Luogu 上的分級，由簡單到困難分別為 🔴🟠🟡🟢🔵🟣⚫。

🔗 🟢 P2627 [USACO11OPEN] Mowing the Lawn G

tags: `動態規劃(Dynamic Programming)` `單調佇列(Monotone Queue)` `單調佇列優化DP`

題意

給定長度為 $N$ 的數列代表效率值，其中第 $i$ 個元素的值為 $E_i$ 。

你可以從中選擇一些元素，要求任意連續被選的元素數量不超過 $K$ 個。

請計算在此限制下，所能取得的效率值最大總和。

約束條件

$1 \leq N \leq 10^5$
$0 \leq E_i \leq 10^9$

思路：單調佇列優化 DP

設 $f[i]$ 表示前 $i$ 個元素所能取得的效率值最大總和，那麼我們可以決定上一個閒置（不選）的位置 $j$ ，使得 $j$ 滿足：

$i - k \leq j \leq i$ ，即兩個被選元素之間最多間隔 $k$ 個元素（題目條件）
$j$ 可以等於 $i$ ，表示閒置的元素是第 $i$ 個元素

則狀態轉移方程為：

$f[i] = \max_{j = i - k}^{i} \left( f[j - 1] + \sum_{t = j+1}^{i} E_t \right)$

注意轉移時不能取 $f[j]$ ，這是因為根據定義， $f[j]$ 可能包含第 $j$ 個元素，這與我們想要的不選第 $j$ 個元素的定義不符。故為了符合定義，需要取 $f[j-1]$ 。

為了方便計算區間和，定義前綴和：

$s[i] = \sum_{t=1}^{i} E_t$

則狀態轉移可以改寫為：

$f[i] = \max_{j = i - k}^{i} \left( f[j - 1] + s[i] - s[j] \right)$

進一步整理，得到：

$f[i] = s[i] + \max_{j = i - k}^{i} \left( f[j - 1] - s[j] \right)$

注意到查詢區間隨著 $i$ 遞增「向右平移」，且要求在每個 $i$ 求 $\max (f[j-1] - s[j])$ （定義為 $w[j]$ ），因此我們可以利用單調佇列(Monotone Queue) 來動態維護一個遞減序列以便在 $O(1)$ 時間內取得區間內最大值，整體時間複雜度降低至 $O(n)$ 。

但需要注意，按照此定義，當 $j = 0$ 時，需要考慮 $f[-1] - s[0]$ ，會出現下標越界，這裡的處理方式是定義 $w[j] = f[j-1] - s[j]$ ，並且定義 $f[-1] = 0$ ，故 $w[0] = f[-1] - s[0] = 0$ ，這樣可以保證 $w[j]$ 的定義在 $j = 0$ 時是合法的。

複雜度分析

時間複雜度： $O(n)$
空間複雜度： $O(n)$

from collections import deque

n, k = map(int, input().split())
E = [0] + [int(input()) for _ in range(n)]

s = [0] * (n + 1)
for i in range(1, n + 1):
    s[i] = s[i - 1] + E[i]

f = [0] * (n + 1)  # 定義 f[-1] = 0
w = [0] * (n + 1)  # w[j] = f[j-1] - s[j], w[0] = f[-1] - s[0] = 0

q = deque([0])  # 單調遞減佇列
for i in range(1, n + 1):
    # 1. 由於轉移時包含當前位置，故需要先計算 w[i]
    w[i] = f[i-1] - s[i]
    while q and w[q[-1]] <= w[i]:
        q.pop()
    q.append(i)

    # 2. 刪除不在窗口範圍 [max(0, i-K), i] 內的索引
    while q and q[0] < i - k:
        q.popleft()
    
    # 3. 根據單調佇列中保存的最大值計算 f[i]
    # f[i] = s[i] + max(f[j-1] - s[j]), for j in [i - k, i]
    f[i] = s[i] + w[q[0]]

print(f[n])

類題

🔴 239. Sliding Window Maximum

寫在最後

PROMPT

masterpiece, best quality, high quality, highres, extremely detailed CG unity 8k wallpaper, extremely detailed, High Detail, vibrant colors, anime style, cover art,

1girl, solo, Koyori, Hakui Koyori, Hakui Koyori (hololive), pink hair, long hair, braids in hair, purple eyes, fox ears, fox tail, black choker, white short-sleeved blouse, pink bow, pink trim on blouse, pink and purple plaid pleated skirt, white thigh garter on left leg, white knee-high socks, lace-trimmed socks, brown loafers,

reaching up to touch cherry blossoms, sitting on stone wall, spring season, cherry blossom trees in full bloom, soft dreamy lighting, urban background with buildings, gentle breeze, sakura petals falling, peaceful atmosphere, outdoors, clear spring day, looking up with wonder

In this enchanting spring scene, Hakui Koyori sits gracefully on a stone wall beneath a canopy of blooming cherry trees. The soft pink petals create a dreamlike atmosphere around her as she reaches up with one hand to gently touch the blossoms. Her expression captures a moment of serene wonder as she gazes upward at the beautiful sakura, with delicate petals occasionally drifting down in the gentle spring breeze.