LibreOJ 2035 「SDOI2016」征途

首先推一下方差的式子。

设 vi 表示第 i 天走的长度，¯v=1mm∑i=1vi 即 vi 的平均数，v 表示方差。
有

v=1mm∑i=1(vi−¯v)2=1m(m∑i=1v2i−2¯vm∑i=1vi+m¯v2)=1m(m∑i=1v2i)−2m(m∑i=1vi)2+m(1mm∑i=1vi)2=1m(m∑i=1v2i)−2m(m∑i=1vi)2+1m(m∑i=1vi)2=1m(m∑i=1v2i)−1m2(m∑i=1vi)2

于是有 v⋅m2=mm∑i=1v2i−(m∑i=1vi)2。

后面一项与方案无关，也不方便列进转移方程，不如单独提出来。
设 Fi,k 表示前 i 段路，走了 k 天的答案。
有转移方程 Fi,k=min0≤j<i(Fj,k−1+m(sumi−sumj)2)。
其中 sumi=i∑j=1vj。

此时把第二维滚掉，设 fi=Fi,k,gi=Fi,k−1。
方程变为 fi=min0≤j<i(gj+m(sumi−sumj)2)。

对于 0≤k<j<i，假设决策 j 优于决策 k，有 gj+m(sumi−sumj)2≤gk+m(sumi−sumk)2gj+m(sum2i−2sumisumj+sum2j)≤gk+m(sum2i−2sumisumk+sum2k)gj−2m⋅sumisumj+m⋅sum2j≤gk−2m⋅sumisumk+m⋅sum2k(gj+m⋅sum2j)−(gk+m⋅sum2k)≤2m⋅sumi(sumj−sumk)(gj+m⋅sum2j)−(gk+m⋅sum2k)sumj−sumk≤2m⋅sumi

维护一只下凸包即可。

代码：

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