首先推一下方差的式子。
设 \(v_i\) 表示第 \(i\) 天走的长度，\(\overline v = \dfrac 1 m \sum\limits_{i = 1}^m v_i\) 即 \(v_i\) 的平均数，\(v\) 表示方差。
有
\[\begin{align*} v & = \dfrac 1 m \sum\limits_{i = 1}^m (v_i - \overline v)^2 \\ & = \dfrac 1 m (\sum\limits_{i = 1}^m v_i^2 - 2\overline v \sum\limits_{i = 1}^m v_i + m \overline v^2) \\ & = \dfrac 1 m (\sum\limits_{i = 1}^m v_i^2) - \dfrac 2 m (\sum\limits_{i = 1}^m v_i)^2 + m (\dfrac 1 m \sum\limits_{i = 1}^m v_i)^2 \\ & = \dfrac 1 m (\sum\limits_{i = 1}^m v_i^2) - \dfrac 2 m (\sum\limits_{i = 1}^m v_i)^2 + \dfrac 1 {m} (\sum\limits_{i = 1}^m v_i)^2 \\ & = \dfrac 1 m (\sum\limits_{i = 1}^m v_i^2) - \dfrac 1 {m^2} (\sum\limits_{i = 1}^m v_i)^2 \end{align*}\]
于是有 \(v \cdot m^2 = m \sum\limits_{i = 1}^m v_i^2 - (\sum\limits_{i = 1}^m v_i)^2\)。
后面一项与方案无关，也不方便列进转移方程，不如单独提出来。
设 \(F_{i,k}\) 表示前 \(i\) 段路，走了 \(k\) 天的答案。
有转移方程 \(F_{i,k} = \min\limits_{0 \le j < i} (F_{j,k - 1} + m (sum_i - sum_j)^2)\)。
其中 \(sum_i = \sum\limits_{j = 1}^i v_j\)。
此时把第二维滚掉，设 \(f_i = F_{i,k},g_i = F_{i,k - 1}\)。
方程变为 \(f_i = \min\limits_{0 \le j < i} (g_j + m (sum_i - sum_j)^2)\)。
对于 \(0 \le k < j < i\)，假设决策 \(j\) 优于决策 \(k\)，有 \[\begin{align*} g_j + m (sum_i - sum_j)^2 & \le g_k + m (sum_i - sum_k)^2 \\ g_j + m (sum_i^2 - 2 sum_i sum_j + sum_j^2) & \le g_k + m (sum_i^2 - 2 sum_i sum_k + sum_k^2) \\ g_j - 2m \cdot sum_i sum_j + m \cdot sum_j^2 & \le g_k - 2m \cdot sum_i sum_k + m \cdot sum_k^2 \\ (g_j + m \cdot sum_j^2) - (g_k + m \cdot sum_k^2) & \le 2m \cdot sum_i (sum_j - sum_k) \\ \dfrac{(g_j + m \cdot sum_j^2) - (g_k + m \cdot sum_k^2)}{sum_j - sum_k} & \le 2m \cdot sum_i \end{align*}\]
维护一只下凸包即可。
代码： 1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const int N = 3e3;
int n,m;
int q[N + 5],head,tail;
long long sum[N + 5],f[N + 5],g[N + 5];
inline double slope(int x,int y)
{
return (double)(g[x] + sum[x] * sum[x] - g[y] - sum[y] * sum[y]) / (sum[x] - sum[y]);
}
int main()
{
scanf("%d%d",&n,&m);
for(register int i = 1;i <= n;++i)
scanf("%lld",sum + i),sum[i] += sum[i - 1],g[i] = sum[i] * sum[i];
for(register int i = 2;i <= m;++i)
{
q[head = tail = 1] = 0;
for(register int j = 1;j <= n;++j)
{
for(;head < tail && slope(q[head],q[head + 1]) <= 2 * sum[j];++head);
f[j] = g[q[head]] + (sum[j] - sum[q[head]]) * (sum[j] - sum[q[head]]);
for(;head < tail && slope(q[tail - 1],q[tail]) >= slope(q[tail],j);--tail);
q[++tail] = j;
}
for(register int j = 1;j <= n;++j)
g[j] = f[j];
}
printf("%lld\n",m * f[n] - sum[n] * sum[n]);
}