一开始肯定要把题目要求的式子给写出来
我们知道方差的公式(s^2=frac{sumlimits_{i=1}^{m}(x_i-overline x)^2}{m})
题目要乘(m^2)再输出，于是
(m^2s^2=msumlimits_{i=1}^{m}(x_i-overline x)^2)
(=m(sumlimits_{i=1}^{m}x_i^2-2overline{x}sumlimits_{i=1}^{m}x_i+moverline{x}^2))
(=msumlimits_{i=1}^{m}x_i^2-(sumlimits_{i=1}^{m}x_i)^2)
于是只要最小化(sumlimits_{i=1}^{m}x_i^2)即可。
然而选(m)段非常不好办。这时候可以联想到凸优化。设(G_m)表示选(m)段(sumlimits_{i=1}^{m}x_i^2)的最小值，当(m)增大的时候(G_m)显然会减小，凭蒟蒻的感性理解，多分出一段对答案的影响幅度也越来越小，也就是说(G_x)关于(x)的函数图像大概是下凸的。
我们用一个斜率为(mid)的直线去切这个凸包。显然(mid)的下界取([0,1])之间的斜率，是总路程平方级别的，上界是(0)。因为切线在凸包的下方，所以多选一段的代价不是(+mid)而是(-mid)。
update:蒟蒻弃用了用直线切凸包的理解方法，蒟蒻用导数思想理解DP凸优化的思路可以看这里
接下来就是斜率优化的过程。设(f_i)为前(i)条路的最优答案，(x_i)为路程长度的前缀和，写出转移方程
(f_i=minlimits_{j=0}^{i}{f_j-2x_ix_j+x_j^2}+x_i^2)
决策(j)优于(k)当且仅当
(f_j-2x_ix_j+x_j^2<f_k-2x_ix_k+x_k^2)
(frac{f_j+x_j^2-f_k-x_k^2}{x_j-x_k}<2x_i)
于是设(y_i=f_i+x_i^2)，把决策看成点((x_i,y_i))，使用单调队列就OK了。注意这里要记(c_i)表示最优决策下将前(i)条路分出的段数。最后判断(c_n)与(m)的关系来调整斜率。
由于这一题的斜率肯定不会有小数，故也不必担心二分中的一些边界问题。
#include<cstdio>
#define RG register
#define R RG int
#define G c=getchar()
#define Calc(j,k) (y[j]-y[k])/(x[j]-x[k])
typedef long long LL;
const int N=3009;
int n,q[N],c[N];
double f[N],k[N],x[N],y[N];
inline int in(){
RG char G;
while(c<'-')G;
R x=c&15;G;
while(c>'-')x=x*10+(c&15),G;
return x;
}
inline double sqr(RG double x){
return x*x;
}
inline void work(R mid){//斜率优化
R h,t,i;
for(h=t=i=1;i<=n;++i){
while(h<t&&k[h]<2*x[i])++h;
f[i]=f[q[h]]+sqr(x[i]-x[q[h]])-mid;//每转移一次要减一下mid
y[i]=f[i]+sqr(x[i]);
c[i]=c[q[h]]+1;//记录段数
while(h<t&&k[t-1]>Calc(q[t],i))--t;
k[t]=Calc(q[t],i);q[++t]=i;
}
}
int main(){
n=in();R m=in(),l,r,mid,i;
for(i=1;i<=n;++i)x[i]=x[i-1]+in();
l=-sqr(x[n]);r=0;//大致确定下界
while(l<r){
work(mid=(l+r+1)/2);//注意负数的下取整问题
c[n]<=m?l=mid:r=mid-1;
}
work(l);
printf("%.0lf
",m*(f[n]+m*l)-sqr(x[n]));//先加回m*l
return 0;
}