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

🔗 P1725 琪露诺

Problem Statement

題目簡述

河岸上的格子編號為 00 到 NN，起點在 00，且 A0=0A_0=0。
每次若目前在格子 ii，下一步只能跳到區間 [i+L,i+R][i+L, i+R] 內的任一格，並獲得落點格子的冰凍指數。
只要下一步能跳到編號大於 NN 的位置，就算成功到達對岸。

請求出在最佳走法下，能取得的最大冰凍指數總和。

Constraints

約束條件

  • 1≤N≤2×1051 \le N \le 2\times 10^5
  • 1≤L≤R≤N1 \le L \le R \le N
  • −103≤Ai≤103-10^3 \le A_i \le 10^3
  • A0=0A_0 = 0
  • 保證最終答案不超過 231−12^{31}-1

思路：單調佇列優化DP

1. 狀態與轉移：每一步只看「可轉移來源」的最大值

把「走到某格子時的最佳總分」當成狀態值。

令 f[i]f[i] 表示「最後停在格子 ii 時，可以取得的最大冰凍指數總和」。

若最後一步落在 ii，上一個落點必須能一步跳到 ii。由於每次跳躍長度介於 LL 到 RR，反推上一格的位置範圍就是：

i−R≤j≤i−Li-R \le j \le i-L

因此轉移為：

f[i]=Ai+max⁡i−R≤j≤i−Lf[j]f[i] = A_i + \max_{i-R \le j \le i-L} f[j]

起點在 00 且 A0=0A_0=0，所以：

f[0]=0f[0] = 0

不可達狀態

有些格子根本到不了，對應的狀態值應視為 −∞-\infty，避免被拿來轉移造成錯誤。

2. 為什麼需要優化：樸素轉移太慢

若每個位置都暴力枚舉所有合法的上一格，單次要掃描大約 R−L+1R-L+1 個候選，總複雜度為：

O(N(R−L+1))\mathcal{O}(N(R-L+1))

在 N≤2×105N \le 2\times 10^5 時會超時。

3. 單調佇列的切入點：滑動窗口區間最大值

觀察轉移式其實只是在問：

max⁡i−R≤j≤i−Lf[j]\max_{i-R \le j \le i-L} f[j]

也就是「隨著 ii 右移的窗口 [i−R,i−L][i-R, i-L] 中，狀態值的最大值」。這正是單調佇列能做到攤還 O(1)\mathcal{O}(1) 查詢的情境。

做法是用雙端佇列維護一串「可能成為最佳上一格的位置」，並維持兩個不變量：

  1. 佇列中的下標都落在當前合法窗口內（過期就從前端丟掉）。
  2. 佇列對應的狀態值單調遞減（新加入的若更好，就把後端較差的候選移除）。

如此一來，佇列前端永遠是窗口內狀態值最大的候選，因此每個 ii 都能在常數時間拿到最佳轉移來源。

關鍵結論

把「轉移來源區間的最大值」改用單調佇列維護後，每個位置只需要常數攤還時間就能完成轉移，整題變成線性時間。

4. 終點判定：哪些格子可能是最後落點？

題目判定成功的條件是「存在一步能跳到編號大於 NN 的位置」。

若目前停在格子 ii，只要：

i+R>Ni + R > N

就能在下一步跳出河岸。

等價於：

i≥N−R+1i \ge N - R + 1

所以答案是區間 [N−R+1,N][N-R+1, N] 中所有可達狀態值的最大者。

複雜度分析

  • 時間複雜度：O(N)\mathcal{O}(N)
  • 空間複雜度：O(N)\mathcal{O}(N)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
from collections import deque


def solve():
    n, L, R = map(int, input().split())
    A = list(map(int, input().split()))
    assert len(A) == n + 1

    f = [0] + [float("-inf")] * n
    q = deque()
    for i, x in enumerate(A):
        # for j in range(max(0, i - R), i - L + 1):
        #     f[i] = max(f[i], f[j] + x)

        # 1. 入窗口，維護窗口內的最大值單調佇列
        if i - L >= 0:
            while q and f[q[-1]] <= f[i - L]:
                q.pop()
            q.append(i - L)
        # 2. 出窗口，移除過期元素
        while q and q[0] < i - R:
            q.popleft()
        # 3. 更新答案
        if q:
            f[i] = max(f[i], f[q[0]] + x)

    # 只有滿足 i + R > n 的 f[i] 可能為答案
    print(max(f[n - R + 1 :]))


if __name__ == "__main__":
    solve()