题目

题目描述

Pine开始了从$S$地到$T$地的征途
从$S$地到$T$地的路可以划分成$n$段，相邻两段路的分界点设有休息站
Pine计划用$m$天到达$T$地。除第$m$天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天中走完
Pine希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小
帮助Pine求出最小方差是多少
设方差是$v$，可以证明，$v \times m ^ 2$是一个整数。为了避免精度误差，输出结果时输出$v \times m ^ 2$

输入格式

第一行两个数$n$、$m$
第二行$n$个数，表示$n$段路的长度

输出格式

一个数，最小方差乘以$m ^ 2$后的值

样例

样例输入

5 2
1 2 5 8 6

样例输出

数据范围与提示

对于$30%$的数据，$1 \leqslant n \leqslant 10$
对于$60%$的数据，$1 \leqslant n \leqslant 100$
对于$100%$的数据，$1 \leqslant n \leqslant 3000$
保证从$S$到$T$的总路程不超过$30000$

来源

SDOI2016 Round1 Day2

题解

首先，我们先把结果的表达式化简一下
假设第$i$天走了$x_i$，总路程为$S$
那么$ans=m^2\times \frac{\sum \limits_{i=1}^m(x_i-\frac{S}{m})^2}{m}=\frac{\sum\limits_{i=1}^m(mx_i-S)^2}{m}=\frac{m^2\sum \limits_{i=1}^mx_i^2+S^2m-2Sm\sum \limits_{i=1}^mx_i}{m}=m\sum \limits_{i=1}^{m}x_i^2+S^2-2S^2=m\sum \limits_{i=1}^{m}x_i^2-S^2$
所以，我们只需要计算最小的$\sum \limits_{i=1}^mx_i^2$
假设$f_{i,j}$表示用$j$天走完前$i$段时，最小的$\sum \limits_{k=1}^jx_k^2$的值
为了方便，我们先预处理出$sum_i$表示前$i$段的长度之和
所以，我们就可以写出状态转移方程：$f_{i,j}=\min \limits_{1\leqslant k<i}{f_{k,j-1}+(sum_i-sum_k)^2}$
显然，这么做的时间复杂度太高了，我们需要进行优化
怎么优化呢？我们考虑$k$比$l$优，那么，我们可以得出：
$f_{k,j-1}+sum_k^2+sum_i^2-2sum_ksum_i<f_{l,j-1}+sum_l^2+sum_i^2-2sum_isum_l$
$f_{k,j-1}-f_{l,j-1}+sum_k^2-sum_k^2<2sum_i(sum_k-sum_l)$
$\frac{f_{k,j-1}-f_{l,j-1}+sum_k^2-sum_k^2}{sum_k-sum_l}<2sum_i$
所以，我们就可以进行斜率优化了！
附上代码：

#include<cstdio>
int n,m,l,r;
long long a[3010],sum[3010],f[3010],fl[3010],q[3010];
long long K(int x,int y)
{
    return (fl[y]-fl[x]+sum[y]*sum[y]-sum[x]*sum[x])/(sum[y]-sum[x]);
}
int main()
{
    scanf("%d%d",&n,&m),sum[0]=0;
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]),sum[i]=sum[i-1]+a[i];
    for(int i=1;i<=n;i++) fl[i]=sum[i]*sum[i];
    for(int i=2;i<=m;i++){
        l=r=1,q[l]=i-1;
        for(int j=i;j<=n;j++){
            while(l<r&&K(q[l],q[l+1])<2*sum[j]) l++;
            f[j]=fl[q[l]]+(sum[j]-sum[q[l]])*(sum[j]-sum[q[l]]);
            while(l<r&&K(q[r-1],q[r])>K(q[r],j)) r--;
            q[++r]=j;
        }
        for(int j=1;j<=n;j++) fl[j]=f[j];
    }
    printf("%lld",m*f[n]-sum[n]*sum[n]);
}