被 K-D Tree 虐了一天后继续来 dp 受苦
题意
给定 $n$ 个数，分成 $m$ 组，使得每组之和构成的数组方差最小，输出方差 $\times m^2$ ， $n \le 3000$
做题
考虑把方差转化推式子：
$$
\begin{aligned}
s^2
& = \frac{\sum_{i = 1}^{m} (v_i - \overline{v})^2}{m} \\
& = \frac{m (\overline{v})^2 - 2 \overline{v} \sum_{i = 1}^{m} v_i + \sum_{i = 1}^{m} v_i^2}{m} \\
又有:\overline{v} & = \frac{\sum_{i = 1}^{m} v_i}{m} \\
代入得 s^2
& = \frac{m (\frac{\sum_{i = 1}^{m} v_i}{m})^2 - 2 \frac{\sum_{i = 1}^{m} v_i}{m} \sum_{i = 1}^{m} v_i + \sum_{i = 1}^{m} v_i^2}{m} \\
& = \frac{\frac{(\sum_{i = 1}^{m} v_i)^2}{m} - 2 \frac{(\sum_{i = 1}^{m} v_i)^2}{m} + \sum_{i = 1}^{m} v_i^2}{m} \\
故 Ans
& = s^2 \times m^2 \\
& = m \sum_{i = 1}^{m} v_i^2 -(\sum_{i = 1}^{m} v_i)^2 \\
& = m \sum_{i = 1}^{m} v_i^2 -(\sum_{i = 1}^{n} x_i)^2 \\
\end{aligned}
$$
发现减号右边的值是恒定的，现在要最小化 $\sum_{i = 1}^{m} v_i^2$
考虑 dp ，设 d[i][j] 表示“把前 $i$ 个数分成 $j$ 段的最小平方和”，转移就预处理前缀和， $O(n)$ 枚举最后一段的长度，时间复杂度为 $O(n^2 m)$ ， TLE $80pts$
观察 dp 方程： $d[i][j] = min(d[k][j - 1] + (sum[i] - sum[k])^2)$ ，考虑斜率优化，设 $t$ 比 $k$ 优，则：
$$
\begin{aligned}
d[t][j - 1] + (sum[i] - sum[t])^2 & < d[k][j - 1] + (sum[i] - sum[k])^2 \\
d[t][j - 1] + sum[t]^2 - d[k][j - 1] - sum[k]^2 & < 2 sum[i] (sum[t] - sum[k]) \\
\frac{(d[t][j - 1] + sum[t]^2) - (d[k][j - 1] + sum[k]^2)}{(sum[t] - sum[k])} & < 2 sum[i]
\end{aligned}
$$
换句话说，把二元组 $(sum[x], d[x][j - 1] + sum[x]^2)$ 看作平面上的点，则点 $(sum[t], d[t][j - 1] + sum[t]^2)$ 比 $(sum[k], d[k][j - 1] + sum[k]^2)$ 优的充要条件（因为以上推导显然可以反向）是两点连线（ $k \to t$ ）的斜率小于 $2 sum[i]$ ，则启发我们将式子化为：
$$
\begin{aligned}
(d[k][j - 1] + sum[k]^2) & = (2sum[i]) \times (sum[k]) + (d[i][j] - sum[i]^2) \\
y & = k \times x + b
\end{aligned}
$$
要想斜率优化，还要保证 $k, x$ 单调递增，而它们都是前缀和，单调性显然，于是就可以（痛苦）快乐的用斜率优化，维护一个凸包，把第二维滚动压掉（只会从 $j - 1$ 到 $j$ ），以第二维为最外层循环，枚举第一维，用单调队列维护凸包，转移时直接取队头，时间复杂度为 $O(mn)$
代码
1 |
|