Luogu 🟢 P2627 [USACO11OPEN] Mowing the Lawn G

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

🔗 🟢 P2627 [USACO11OPEN] Mowing the Lawn G

Problem Statement

題目簡述

有 $N$ 隻排成一排的奶牛，每隻奶牛有其對應的效率值 $E_i$。我們需要從中挑選若干隻奶牛，使得任意連續被選中的奶牛數量不超過 $K$ 隻。求能獲得的最大效率總和。

Constraints

約束條件

• $1 \le N \le 10^5$
• $1 \le K \le N$
• $0 \le E_i \le 10^9$

---

思路：單調佇列優化 DP

1. 狀態設計：枚舉上一頭休息的奶牛

這題的限制是：不能選出超過 $K$ 隻連續的奶牛。換句話說，如果目前考慮到第 $i$ 隻奶牛，最後一段被選中的奶牛長度不能超過 $K$。

設 $f[i]$ 表示前 $i$ 隻奶牛最多能獲得的總效率。為了描述最後一段連續被選中的奶牛，我們枚舉「上一頭休息的奶牛」的位置 $j$。

若第 $j$ 隻奶牛休息，則第 $j+1$ 隻到第 $i$ 隻奶牛都可以被選中。為了不違反連續數量限制，位置 $j$ 必須滿足：

• $i-K \le j \le i$，也就是最後連續被選中的奶牛數量不超過 $K$。
• $j$ 可以等於 $i$，表示第 $i$ 隻奶牛本身休息，此時最後一段被選中的奶牛數量為 $0$。

因此，狀態轉移可以寫成：

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

其中，$E_t$ 表示第 $t$ 隻奶牛的效率。

為什麼這樣枚舉是完整的？

任一合法方案在前 $i$ 隻奶牛中，都可以看成「前面一段合法方案」加上「最後一段連續被選中的奶牛」。
只要找到最後一段開始前那頭休息的奶牛，就能唯一描述這次轉移；而 $j=i$ 又涵蓋了「目前這頭不選」的情況。

---

2. 前綴和化簡轉移式

直接計算區間效率和會讓每次轉移都需要額外枚舉一段區間。為了把區間和變成 $\mathcal{O}(1)$ 查詢，定義前綴和：

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

那麼第 $j+1$ 隻到第 $i$ 隻奶牛的效率和就是：

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

代入原本的狀態轉移：

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

由於 $s[i]$ 對所有候選的 $j$ 都相同，可以提出到最大值外面：

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

這一步是整題的關鍵：我們不再需要重新計算每段連續奶牛的效率，只需要在一個會滑動的區間中，找出 $f[j-1] - s[j]$ 的最大值。

---

3. 單調佇列優化

令輔助狀態值為：

$$w[j] = f[j-1] - s[j]$$

則轉移式可以寫成：

$$f[i] = s[i] + \max_{j = i-K}^{i} w[j]$$

可復用模型

如果 DP 轉移長得像「目前位置的固定項 + 某個滑動窗口內的最大值 / 最小值」，通常就可以考慮用單調佇列優化。

本題中，隨著目前位置 $i$ 往右移動，查詢區間 $[i-K, i]$ 也會同步向右平移，所以正好是滑動窗口最大值模型。

我們維護一個雙端佇列，佇列中保存候選位置，並讓這些位置對應的輔助狀態值保持單調遞減。這樣一來，佇列頭部就永遠是目前窗口內的最大值。

每處理一個新位置時，需要做三件事：

1. 先計算目前位置作為「休息位置」時的輔助狀態值，並加入佇列。
2. 加入前從佇列尾部移除所有不如目前位置優的候選，維持單調遞減。
3. 從佇列頭部移除已經不在 $[i-K, i]$ 範圍內的候選。

完成後，佇列頭部對應的輔助狀態值就是轉移所需的最大值。

---

注意事項：$j=0$ 的邊界

按照上述定義，當 $j=0$ 時，需要使用：

$$f[-1] - s[0]$$

這在一般陣列下標中會出現越界。為了讓轉移在邊界處也一致，我們額外定義：

$$w[0] = 0$$

可以理解為：在還沒選任何奶牛之前，前面的最大效率是 $0$，前綴和也是 $0$。這樣一來，當前 $i$ 隻奶牛全部都被選中且 $i \le K$ 時，也能透過 $j=0$ 這個候選位置自然轉移得到答案。

佇列一開始必須放入位置 $0$，否則前 $K$ 隻奶牛全部被選中的情況就無法被正確轉移到。

複雜度分析

• 時間複雜度：$\mathcal{O}(N)$。每隻奶牛的下標最多入隊一次、出隊一次，單調佇列的操作均攤為 $\mathcal{O}(1)$，因此總時間複雜度為線性。
• 空間複雜度：$\mathcal{O}(N)$。需要前綴和陣列、DP 狀態陣列、輔助狀態陣列以及單調佇列，空間複雜度為線性。

---

Code

from collections import deque

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

# 計算前綴和，方便 O(1) 查詢區間和
s = [0] * (n + 1)
for i in range(1, n + 1):
    s[i] = s[i - 1] + E[i]

# f[i] 表示前 i 隻奶牛在滿足限制下的最大總效率
f = [0] * (n + 1)  # 定義 f[-1] = 0
# w[j] = f[j-1] - s[j] 為輔助狀態值，w[0] = f[-1] - s[0] = 0
w = [0] * (n + 1)

# 單調佇列，維護 w[j] 的最大值，佇列中保存下標，對應的 w 值單調遞減
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. 刪除不在窗口範圍 [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])