题目理解

我们需要将 $n$ 段路分成 $m$ 天走完，要求每天走的路程长度的方差最小。

设第 $i$ 天走的路程为 $x_i$，平均值为 $\bar{x} = \frac{\text{总路程}}{m}$，则方差为： [ v = \frac{1}{m} \sum_{i=1}^m (x_i - \bar{x})^2 ]

题目要求输出 $v \times m^2$。

---

方差公式化简

设总路程 $S = \sum_{i=1}^n a_i$，则 $\bar{x} = \frac{S}{m}$。

方差： [ v = \frac{1}{m} \sum_{i=1}^m \left(x_i - \frac{S}{m}\right)^2 ]

乘以 $m^2$： [ v \times m^2 = m \sum_{i=1}^m \left(x_i - \frac{S}{m}\right)^2 ]

展开： [ = m \sum_{i=1}^m \left(x_i^2 - 2x_i \cdot \frac{S}{m} + \frac{S^2}{m^2}\right) ] [ = m \sum_{i=1}^m x_i^2 - 2S \sum_{i=1}^m x_i + m \cdot \frac{S^2}{m} ] [ = m \sum_{i=1}^m x_i^2 - 2S \cdot S + S^2 ] [ = m \sum_{i=1}^m x_i^2 - S^2 ]

因此，最小化 $v \times m^2$ 等价于最小化 $\sum_{i=1}^m x_i^2$。

---

问题转化

原问题转化为：将 $n$ 段路划分成 $m$ 个连续区间，使得每个区间的长度平方和最小。

设 $pre[i]$ 表示前 $i$ 段路的总长度，即前缀和。

则问题变成：在 $pre[0], pre[1], \dots, pre[n]$ 中选择 $m$ 个分割点（包括首尾），将序列分成 $m$ 段，最小化： [ \sum_{j=1}^m (pre[r_j] - pre[l_j])^2 ] 其中 $l_j, r_j$ 是第 $j$ 段的起止位置。

---

动态规划设计

状态定义

设 $dp[i][k]$ 表示将前 $i$ 段路分成 $k$ 天的最小平方和。

状态转移

[ dp[i][k] = \min_{j < i} { dp[j][k-1] + (pre[i] - pre[j])^2 } ] 其中 $j$ 是上一段的结束位置。

初始化

• $dp[0][0] = 0$
• 其他初始化为无穷大

答案

最终答案 = $m \times dp[n][m] - S^2$

---

斜率优化

直接 DP 的复杂度是 $O(n^2 m)$，对于 $n, m \leq 3000$ 会超时。

观察转移方程： [ dp[i][k] = \min_{j < i} { dp[j][k-1] + pre[i]^2 - 2pre[i]pre[j] + pre[j]^2 } ] [ = pre[i]^2 + \min_{j < i} { dp[j][k-1] + pre[j]^2 - 2pre[i]pre[j] } ]

令：

• $X(j) = pre[j]$
• $Y(j) = dp[j][k-1] + pre[j]^2$
• $K(i) = 2pre[i]$

则： [ dp[i][k] = pre[i]^2 + \min_{j < i} { Y(j) - K(i)X(j) } ]

这正好是斜率优化的标准形式：最小化截距 $Y(j) - KX(j)$。

---

斜率优化实现

维护一个凸壳，使得斜率单调递增。

对于当前层 $k$：

1. 在队列中维护可能的决策点 $j$
2. 当队首两点斜率小于 $K(i)$ 时，弹出队首（因为 $K(i)$ 随 $i$ 递增）
3. 队首即为最优决策
4. 将 $i$ 加入队列前，维护凸壳性质

---

复杂度分析

• 斜率优化后，每层 DP 复杂度 $O(n)$
• 总复杂度 $O(nm)$
• 对于 $n, m \leq 3000$ 可以接受

---

样例验证

输入：

5 2
1 2 5 8 6

计算过程：

• 前缀和 $pre = [0, 1, 3, 8, 16, 22]$
• 总路程 $S = 22$
• 分成 2 天的最优划分：第一天 $[1,2,5]$（长度8），第二天 $[8,6]$（长度14）
• 平方和 $8^2 + 14^2 = 64 + 196 = 260$
• 答案 = $2 \times 260 - 22^2 = 520 - 484 = 36$

输出：36 ✓

---

公式总结

关键推导： [ v \times m^2 = m \sum_{i=1}^m x_i^2 - S^2 ] 其中 $S = \sum_{i=1}^n a_i$。

因此只需最小化 $\sum_{i=1}^m x_i^2$，使用斜率优化 DP。

---

总结

本题的关键在于：

1. 将方差公式化简为平方和最小化问题
2. 识别出可以使用动态规划求解
3. 应用斜率优化降低复杂度
4. 注意前缀和的使用和边界条件处理

这是一个经典的斜率优化 DP 问题，考察了数学公式化简和动态规划优化的能力。