🔗 AWC0096D Hiking and Rest

Problem Statement

題目簡述

高橋從海拔 $0$ 開始爬山，路線分成 $N$ 段。通過第 $i$ 段後，海拔會增加 $D_i$ ；若變化後小於 $0$ ，則海拔會被修正為 $0$ ，也就是新海拔為 $\max(h + D_i, 0)$ 。

爬山途中必須恰好使用一次纜車。使用纜車時，當前海拔 $h$ 會立刻變成 $\left\lfloor \frac{h}{2} \right\rfloor$ 。纜車可以在第 $1$ 段前、任兩段之間，或第 $N$ 段後使用。求最優使用時機下，完成所有路段後的最小海拔。

Constraints

約束條件

$1 \le N \le 5 \times 10^5$
$-10^9 \le D_i \le 10^9$
所有輸入皆為整數

思路：狀態機DP

這題涉及一個典型套路：操作「恰好一次」，且操作位置可以插在任意兩個元素之間。直接枚舉纜車使用位置，再從頭模擬到尾，會是 $\mathcal{O}(N^2)$ ，無法承受。

關鍵在於，走到某個位置後，對未來有用的資訊其實很少。不妨定義：

$f[i][0]$ ：走完前 $i$ 段，且尚未使用纜車時，能得到的海拔。
$f[i][1]$ ：走完前 $i$ 段，且已經使用纜車時，能得到的最小海拔。

其中 $f[i][0]$ 沒有分支，因為纜車還不能用； $f[i][1]$ 則把「纜車在哪個位置使用」這個選擇壓縮成一個最小值。

貪心的正確性

高度轉移 $h \mapsto \max(h + x, 0)$ 對 $h$ 是單調不減的。也就是說，在纜車已使用的情況下，當前海拔越低，走完後面路段也不會變得更差。因此只保留最小可能海拔是安全的。

狀態轉移

先看「尚未使用纜車」的狀態。走完第 $i$ 段後只能照普通爬山規則更新：

f[i][0] = \max(f[i - 1][0] + D_i, 0)

再看「已經使用纜車」的狀態。它有兩種來源：

纜車早在之前就用過，現在只是繼續通過當前路段。
纜車在當前路段之後使用，於是從尚未使用纜車的海拔立刻折半。

對應轉移為：

f[i][1] = \min\left(\max(f[i - 1][1] + D_i, 0),\ \left\lfloor \frac{f[i][0]}{2} \right\rfloor\right)

第一項表示「之前已經使用纜車，現在走第 $i$ 段」；第二項表示「先正常走完第 $i$ 段，再立刻使用纜車」。兩者取較小值，就是走到目前位置後、纜車已使用時的最佳海拔。

滾動陣列壓縮

實作時不需要真的開二維陣列。因為每次轉移只依賴上一段的狀態，所以用兩個變數壓縮：

h0 對應目前的 $f[i][0]$ ，初始為 $f[0][0] = 0$ 。
h1 對應目前的 $f[i][1]$ ，初始為 $f[0][1] = 0$ ，表示出發前已經使用纜車。
每讀到一段變化量，就先更新尚未使用纜車的高度，再更新已使用纜車的最小高度。

由於在第

1

段前就可以使用纜車，所以初始值

f[0][1] = 0

，表示「出發前已經使用纜車」。

複雜度分析

時間複雜度： $\mathcal{O}(N)$
空間複雜度： $\mathcal{O}(N)$ ，因為程式保存了整個變化序列；若讀入後直接迭代原序列，也可視為只需 $\mathcal{O}(1)$ 額外狀態

Code

def solve():
    n = int(input())
    D = list(map(int, input().split()))
    assert len(D) == n

    h0 = h1 = 0
    for d in D:
        h0 = max(h0 + d, 0)
        h1 = max(h1 + d, 0)
        h1 = min(h1, h0 // 2)
    print(h1)


if __name__ == "__main__":
    solve()