自动搬运

查看原文

来自洛谷，原作者为

	Dispwnl **

搬运于2025-08-24 21:56:12，当前版本为作者最后更新于2018-03-22 20:05:57，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

原先修改的公式还是有误，已修改

求方差……先搞式子

已知： $s^{2}=\frac {(\overline v-v_1)^{2}+(\overline v-v_2)^{2}+...+(\overline v-v_m)^{2}}{m}$

然后：$s^{2}=\frac {(\frac {\sum_{i=1}^{m}v_i}{m} -v_1)^{2}+(\frac {\sum_{i=1}^{m}v_i}{m} -v_2)^{2}+...+(\frac {\sum_{i=1}^{m}v_i}{m} -v_m)^{2}}{m}$

展开：$s^{2}=\frac {m\times \frac {(\sum_{i=1}^{m}v_i)^{2}}{m^{2}}-2\times\frac {(\sum_{i=1}^{m}v_i)}{m}\times (v_1+v_2+...+v_m)+(v_1^{2}+v_2^{2}+...+v_m^{2})}{m}$

然后可化为： $s^{2}=\frac {\frac {(\sum_{i=1}^{m}v_i)^{2}}{m}-2\times \frac {(\sum_{i=1}^{m}v_i)^{2}}{m}+(v_1^{2}+v_2^{2}+...+v_m^{2})}{m}$

然后： $s^{2}=-\frac {(\sum_{i=1}^{m}v_i)^{2}}{m^{2}}+\frac {(v_1^{2}+v_2^{2}+...+v_m^{2})}{m}$

还要$\times m^2$

$s^{2}\times m^{2}=-(\sum_{i=1}^{m}v_i)^{2}+m\times (v_1^{2}+v_2^{2}+...+v_m^{2})$

这样就好了，你会发现式子右边第一项是个定值，而第二项我们可以用前缀和搞搞

用$f_{i,l}$表示前$i$段分为$l$天走的最小平方和（这里也是平方了因为最后处理成方差了QAQ）

即有：$f_{i,l}=min(f_{i,l},f_{j,l-1}+(sum_i-sum_j)^{2})(0\le j<i)$（$m$可以最后乘上）

然后$80$分到手

可以发现这个式子可以用斜率优化搞，即可以这么化：

$f_{i,l}+2\times sum_i\times sum_j=f_{j,l-1}+sum_i^{2}+sum_j^{2}$

然后就是斜率优化套路了

代码：

# include<iostream>
# include<cstring>
# include<cstdio>
# define LL long long
using namespace std;
const int MAX=3e3+1;
int n,m;
int qu[MAX];
LL sum[MAX],f[MAX],g[MAX];
int read()
{
    int x=0;
    char ch=getchar();
    for(;!isdigit(ch);ch=getchar());
    for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
    return x;
}
double X(int i)
{
    return sum[i];
}
double Y(int i)
{
    return g[i]+sum[i]*sum[i];
}
double look(int x,int y)
{
    return (Y(x)-Y(y))/(X(x)-X(y));
}
int main()
{
    n=read(),m=read();
    for(int i=1;i<=n;++i)
      sum[i]=sum[i-1]+read(),g[i]=sum[i]*sum[i];
    for(int l=1;l<m;++l)
      {
      	int he=1,ta=1;
      	qu[1]=l;
      	for(int i=l+1;i<=n;++i)
          {
          	while(he<ta&&look(qu[he],qu[he+1])<2*sum[i]) ++he;
          	int tt=qu[he];
          	f[i]=g[tt]+(sum[i]-sum[tt])*(sum[i]-sum[tt]);
          	while(he<ta&&look(qu[ta],qu[ta-1])>look(qu[ta],i)) --ta;
          	qu[++ta]=i;
          }
        for(int i=1;i<=n;i++)
          g[i]=f[i];
      }
    printf("%lld",-sum[n]*sum[n]+m*f[n]);
    return 0;
}