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

🔗 🟣 P3195 [HNOI2008] 玩具装箱

Problem Statement

題目簡述

有 $n$ 個玩具，必須按照原本順序分成若干個連續段，每一段放進一個容器。
若一個容器裝下標 $i$ 到 $j$ 的玩具，容器長度為

(j-i)+\sum_{k=i}^{j} C_k

其中相鄰兩個玩具之間需要 $1$ 單位填充物。容器長度為 $x$ 時，費用為 $(x-L)^2$ 。
求所有容器費用總和的最小值。

Constraints

約束條件

$1 \le n \le 5\times 10^4$
$1 \le L \le 10^7$
$1 \le C_k \le 10^7$ ， $0 \le k < n$

思路：劃分型 DP → 斜率優化/凸包優化(Convex Hull Trick)

先寫出自然 DP

這題的核心是：把一個序列切成若干個連續段，每段有一個只和段內總長度有關的代價，求總代價最小。這是典型的劃分型 DP。

先看最後一箱。若前面已經處理完前若干個玩具，最後一箱裝的是後面一段連續玩具，那麼答案可以由「前綴的最小代價 + 最後一箱的代價」轉移而來。

令前綴長度和為 $S_i=\sum_{k=0}^{i-1} C_k$ ，並定義 $f_i$ 表示裝完前 $i$ 個玩具，也就是下標區間 $[0,i)$ 的最小代價。若最後一箱裝的是下標區間 $[j,i)$ ，這箱的玩具總長度是 $S_i-S_j$ ，中間填充物有 $i-j-1$ 個，所以這箱的費用是

\left((i-j-1)+(S_i-S_j)-L\right)^2

因此有轉移：

f_i=\min_{0\le j<i}\left\{f_j+\left((i-j-1)+(S_i-S_j)-L\right)^2\right\}

直接枚舉每個 $i$ 的所有 $j$ 是 $\mathcal{O}(n^2)$ ，而 $n$ 到 $5\times 10^4$ ，需要優化內層的最小值查詢。

題型入口

看到「前綴最小值 + 某段代價」，先寫出劃分型 DP；如果段代價展開後有二次項，常見方向就是把轉移式整理成一次函數或內積形式，用斜率優化 / 凸包優化處理。

把二次式整理成內積

Convex Hull Trick 觀念引用

這一段會用到和 LeetCode 🔴 3826. Minimum Partition Score 相同的 CHT 觀念：把 DP 轉移中的枚舉項改寫成「一組候選點」與「一個查詢向量」的內積，之後只需要在凸包上找內積最小的點。

先把最後一箱的式子壓縮一下。對固定的右端點 $i$ ，有

(i-j-1)+(S_i-S_j)-L =(i+S_i)-(j+S_j+L+1)

不妨定義

A_i=i+S_i,\qquad B_j=j+S_j+L+1

則轉移變成

f_i=\min_{0\le j<i}\left\{f_j+(A_i-B_j)^2\right\}

展開平方：

\begin{aligned} f_i &=\min_{0\le j<i}\left\{f_j+A_i^2-2A_iB_j+B_j^2\right\}\\ &=A_i^2+\min_{0\le j<i}\left\{f_j+B_j^2-2A_iB_j\right\} \end{aligned}

現在，和目前右端點有關的 $A_i^2$ 已經被提出去了；剩下要做的是，從所有歷史決策中找一個讓

f_j+B_j^2-2A_iB_j

最小的決策。

定義每個歷史決策對應的候選點為

v_j=\left(B_j,\; f_j+B_j^2\right)

定義目前右端點對應的查詢向量為

p_i=(-2A_i,\;1)

那麼內層最小值就是

\min_{0\le j<i} p_i\cdot v_j

也就是查詢向量與候選點的內積最小值。

因此，這個轉移已經變成標準的 CHT 查詢形式：答案只可能出現在下凸包上。

幾何意義

對同一個查詢向量來說，最小化內積可以理解成找投影最小的候選點。凸包內部的點一定會被凸包邊界上的某些點支配，因此不可能成為最優決策。於是我們只需要維護下凸包，而不是保留所有歷史點逐一比較。

為什麼可以依序加入候選點？

程式每算到新的位置，就把「前一個位置作為最後一箱起點前綴」的候選點加入凸包，再查詢目前位置的答案。這樣保證查詢時凸包中剛好包含所有合法的 $j<i$ 。

候選點的橫座標是

B_j=j+S_j+L+1

因為每個玩具長度都是正數， $S_j$ 隨著 $j$ 嚴格遞增，所以 $B_j$ 也嚴格遞增。這正好滿足 Andrew 式維護下凸包的前提：點按照橫座標遞增加入，不需要額外排序。

維護時看最後兩個凸包點與新點的轉向。如果中間點讓下凸包不再凸，代表它不可能在任何查詢中成為最優點，就可以刪除。程式中的外積判斷做的就是這件事。

查詢方式：二分，或利用單調性改成隊列

本份程式實際呼叫的是 query_bisect()。對固定查詢向量，凸包頂點上的內積值會先下降再上升，所以可以二分找到最小點，單次查詢 $\mathcal{O}(\log n)$ 。

但本題還有更強的單調性，可以把查詢改成註解中的 query_mono()。

目前位置往右移時，

A_i=i+S_i

嚴格遞增，因此查詢向量

(-2A_i,\;1)

的第一維嚴格遞減，第二維不變。也就是說，查詢方向只會往同一側旋轉。

在一個按橫座標遞增的下凸包上，查詢方向單調旋轉時，最優頂點的索引也只會往右移，不會往左退。於是如果當前隊首已經不如下一個點，即

p\cdot q_0 \ge p\cdot q_1

那麼之後查詢方向繼續單調變化， $q_0$ 也不可能重新變成最優點，可以永久彈出。這就是單調隊列查詢的正確性來源。

實作對應

程式保守使用二分查詢，時間複雜度是 $\mathcal{O}(n\log n)$ 。若把查詢改成已寫好的 query_mono()，由於本題同時滿足「加入點橫座標遞增」與「查詢方向單調」，每個凸包點最多進出隊一次，可降到 $\mathcal{O}(n)$ 。

複雜度分析

時間複雜度： $\mathcal{O}(n\log n)$ ，程式使用凸包上的二分查詢；若改用單調隊列查詢，可做到 $\mathcal{O}(n)$ 。
空間複雜度： $\mathcal{O}(n)$ 。

Code

"""
根據題意，cost(l, r) = ((r - l) + s[r + 1] - s[l] - L)^2，其中 s[i] 是 A 的前綴和。
可以得到轉移式：f[i] = min_{j < i} f[j] + ((i - (j + 1)) + s[i + 1] - s[j + 1] - L)^2

令 a[i] = i + s[i + 1], b[j] = j + s[j + 1] + L + 1，
則轉移式可以寫成 f[i] = min_{j < i} f[j] + (a[i] - b[j])^2
展開後得到 f[i] = min_{j < i} (f[j] + a[i]^2 - 2 * a[i] * b[j] + b[j]^2)，
把與 j 無關的 a[i]^2 提出來，得到 f[i] = a[i]^2 + min_{j < i} (f[j] + b[j]^2 - 2 * a[i] * b[j])，
令 p = (-2 * a[i], 1), vj = (b[j], f[j] + b[j]^2)，則可以使用 CHT 來維護 vj，查詢 min(p·vj)。
"""

from itertools import accumulate
from math import inf
from collections import deque


class Vec:
    __slots__ = "x", "y"

    def __init__(self, x: int, y: int):
        self.x = x
        self.y = y

    def __add__(self, b: "Vec") -> "Vec":
        return Vec(self.x + b.x, self.y + b.y)

    def __sub__(self, b: "Vec") -> "Vec":
        return Vec(self.x - b.x, self.y - b.y)

    def det(self, b: "Vec") -> int:
        return self.x * b.y - self.y * b.x

    def dot(self, b: "Vec") -> int:
        return self.x * b.x + self.y * b.y


class ConvexHull:
    """
    注意：
    - add() 的點需要依 x 遞增加入。
    - query_bisect() 不要求查詢向量單調，使用二分搜尋。
    - query_mono() 使用單調隊列優化，因此查詢向量 p 需要滿足最佳點索引單調往前移動。
    """

    def __init__(self):
        self.hull = deque()

    def add(self, v: Vec) -> None:
        hull = self.hull

        # 如果新點與最後一個點 x 相同，只保留對應 mode 下較優的 y
        if hull and hull[-1].x == v.x:
            if hull[-1].y <= v.y:
                return
            hull.pop()

        # 維護凸包性質，移除不可能成為凸包的中間點
        while len(hull) >= 2 and (hull[-1] - hull[-2]).det(v - hull[-1]) <= 0:
            hull.pop()

        hull.append(v)

    def query_bisect(self, p: Vec) -> int:
        hull = self.hull

        # 使用二分搜尋找到最佳點
        left, right = 0, len(hull) - 2
        while left <= right:
            mid = (left + right) // 2
            curr = p.dot(hull[mid])
            nxxt = p.dot(hull[mid + 1])
            if curr >= nxxt:
                left = mid + 1
            else:
                right = mid - 1

        return p.dot(hull[left])

    def query_mono(self, p: Vec) -> int:
        hull = self.hull

        # 使用單調隊列維護
        while len(hull) >= 2 and p.dot(hull[0]) >= p.dot(hull[1]):
            hull.popleft()
        return p.dot(hull[0])


def solve():
    n, L = map(int, input().split())
    A = [int(input()) for _ in range(n)]

    s = list(accumulate(A, initial=0))

    f = [inf] * (n + 1)
    f[0] = 0

    cht = ConvexHull()
    for i in range(1, n + 1):
        j = i - 1
        b_j = j + s[j] + L + 1
        vj = Vec(b_j, f[j] + b_j * b_j)
        cht.add(vj)

        a_i = i + s[i]
        p = Vec(-2 * a_i, 1)

        best = cht.query_bisect(p)
        # best = cht.query_mono(p)
        f[i] = best + a_i * a_i

    print(f[n])


if __name__ == "__main__":
    solve()