[HNOI2008] 玩具装箱

题目描述

P 教授要去看奥运，但是他舍不下他的玩具，于是他决定把所有的玩具运到北京。他使用自己的压缩器进行压缩，其可以将任意物品变成一堆，再放到一种特殊的一维容器中。

P 教授有编号为 $1 \cdots n$ 的 $n$ 件玩具，第 $i$ 件玩具经过压缩后的一维长度为 $C_i$。

为了方便整理，P教授要求：

• 在一个一维容器中的玩具编号是连续的。
• 同时如果一个一维容器中有多个玩具，那么两件玩具之间要加入一个单位长度的填充物。形式地说，如果将第 $i$ 件玩具到第 $j$ 个玩具放到一个容器中，那么容器的长度将为 $x=j-i+\sum\limits_{k=i}^{j}C_k$。

制作容器的费用与容器的长度有关，根据教授研究，如果容器长度为 $x$，其制作费用为 $(x-L)^2$。其中 $L$ 是一个常量。P 教授不关心容器的数目，他可以制作出任意长度的容器，甚至超过 $L$。但他希望所有容器的总费用最小。

输入格式

第一行有两个整数，用一个空格隔开，分别代表 $n$ 和 $L$。

第 $2$ 到 第 $(n + 1)$ 行，每行一个整数，第 $(i + 1)$ 行的整数代表第 $i$ 件玩具的长度 $C_i$。

输出格式

输出一行一个整数，代表所有容器的总费用最小是多少。

样例 #1

样例输入 #1

5 4
3
4
2
1
4

样例输出 #1

1

提示

对于全部的测试点，$1 \leq n \leq 5 \times 10^4$，$1 \leq L \leq 10^7$，$1 \leq C_i \leq 10^7$。

原式：

$$dp[i] = \min_{j} \left( dp[j] + \left( \sum_{k=j+1}^i a_k + (i-j-1-L) \right)^2 \right) $$

• 定义前缀和 $sum[i] = a_1 + a_2 + \cdots + a_i$，则 $sum[i] - sum[j]$ 是区间 $[j+1, i]$ 的和。
• 令 $f[i] = sum[i] + i,c = 1 + L$，因此，原式中的表达式可简化为：$$dp[i] = \min_{j} \left( dp[j] + (f[i] - f[j] - c)^2 \right) $$

假设条件：

• 对于当前 $i$，若 $j$ 比 $k$ 更优，则：$$dp[j] + (f[i] - f[j] - c)^2 \leq dp[k] + (f[i] - f[k] - c)^2 \quad (1) $$

1. 引入变量 $v$：
   • 设 $f[t] = f[i] + v$，其中 $v = f[t] - f[i] \geq 0$（因 $f$ 单调递增）。
2. 代入式：$$dp[j] + (f[i] + v - f[j] - c)^2 \leq dp[k] + (f[i] + v - f[k] - c)^2 $$
3. 展开平方项：$$\underbrace{dp[j] + (f[i] - f[j] - c)^2}_{\text{式 (1) 左边}} + 2v(f[i] - f[j] - c) + v^2 \leq \underbrace{dp[k] + (f[i] - f[k] - c)^2}_{\text{式 (1) 右边}} + 2v(f[i] - f[k] - c) + v^2 $$
4. 消去相同项 $v^2$，并利用式 (1) 的不等式：$$2v(f[i] - f[j] - c) \leq 2v(f[i] - f[k] - c)$$
5. 简化后得到：$$f[j] \geq f[k]$$

结论： 因 $f$ 单调递增，只需按 $j$ 的顺序枚举（从 $1$ 到 $i-1$），即可保证 $f[j] \geq f[k]$（若 $j > k$）。

展开式 (1)：

$$dp[j] + (f[i] - f[j] - c)^2 \leq dp[k] + (f[i] - f[k] - c)^2 $$

1. 展开平方项：$$dp[j] + f[i]^2 - 2f[i](f[j] + c) + (f[j] + c)^2 \leq dp[k] + f[i]^2 - 2f[i](f[k] + c) + (f[k] + c)^2 $$
2. 消去 $f[i]^2$，移项整理：$$dp[j] - dp[k] + (f[j] + c)^2 - (f[k] + c)^2 \leq 2f[i] \left( f[j] - f[k] \right) $$
3. 将左侧因式分解：$$\frac{(dp[j] + (f[j] + c)^2) - (dp[k] + (f[k] + c)^2)}{2(f[j] - f[k])} \leq f[i] $$
4. 定义斜率形式：$$\text{Slope}(k, j) = \frac{Y_j - Y_k}{X_j - X_k} \quad \text{其中} \ Y_j = dp[j] + (f[j] + c)^2, \ X_j = f[j] $$因此，原式可写为：$$\text{Slope}(k, j) \leq f[i]$$

结论： 当 $\text{Slope}(k, j) \leq f[i]$ 时，$j$ 比 $k$ 更优。

操作规则：

1. 删除队头（冗余决策点）：
   • 若队列前两个点 $q[l], q[l+1]$ 的斜率满足：$$\text{Slope}(q[l], q[l+1]) \leq f[i]$$ 则 $q[l]$ 不如 $q[l+1]$ 优，可删除 $q[l]$。
   2. 删除队尾（非凸性点）：
      • 若队列末尾三个点 $q[r-1], q[r], i$ 的斜率满足：$$\text{Slope}(q[r-1], q[r]) \geq \text{Slope}(q[r], i) $$则 $q[r]$ 的斜率不够“陡”，可删除 $q[r]$，以保持队列的凸性。

依据： 凸包维护的单调队列优化技巧，确保决策点按斜率递增顺序排列 。