题解 P4072 【[SDOI2016]征途】

· · 题解

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

求方差……先搞式子

已知：

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;
}