LibreOJ 2035.「SDOI2016」征途

首先推一下方差的式子。

viv_i 表示第 ii 天走的长度,v=1mi=1mvi\overline v = \dfrac 1 m \sum\limits_{i = 1}^m v_iviv_i 的平均数,vv 表示方差。

于是有 vm2=mi=1mvi2(i=1mvi)2v \cdot m^2 = m \sum\limits_{i = 1}^m v_i^2 - (\sum\limits_{i = 1}^m v_i)^2

后面一项与方案无关,也不方便列进转移方程,不如单独提出来。
Fi,kF_{i,k} 表示前 ii 段路,走了 kk 天的答案。
有转移方程 Fi,k=min0j<i(Fj,k1+m(sumisumj)2)F_{i,k} = \min\limits_{0 \le j < i} (F_{j,k - 1} + m (sum_i - sum_j)^2)
其中 sumi=j=1ivjsum_i = \sum\limits_{j = 1}^i v_j

此时把第二维滚掉,设 fi=Fi,k,gi=Fi,k1f_i = F_{i,k},g_i = F_{i,k - 1}
方程变为 fi=min0j<i(gj+m(sumisumj)2)f_i = \min\limits_{0 \le j < i} (g_j + m (sum_i - sum_j)^2)

对于 0k<j<i0 \le k < j < i,假设决策 jj 优于决策 kk,有

维护一只下凸包即可。

代码:

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
#include <cstdio>
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]);
}