好久没写题解了……

一开始脑抽，还以为平均数会随着划分的改变而改变（无可救药……）

这题还是比较水的，展开方差的式子分成m部分每部分路程为xi,平均数p

方差=∑(xi-p)/m=∑(xi^2-2xi*p+p^2)/m=∑xi^2/m-2*S*p/m+p^2=∑xi^2/m-p^2

所以只要求∑xi^2即可，不难想到f[i,j]=min(f[k,j-1]+sqr(s[i]-s[k])

裸的斜率优化即可

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6  7 using namespace std; 8 int s[3010],g[3010],f[3010],q[3010]; 9 int n,m;10 11 int sqr(int x)12 {13     return x*x;14 }15 double k(int j,int k)16 {17        return (sqr(s[k])-sqr(s[j])+g[k]-g[j])/(s[k]-s[j]);18 }19 20 int main()21 {22     scanf("%d%d",&n,&m);23     for (int i=1; i<=n; i++) 24     {25         scanf("%d",&s[i]);26         s[i]+=s[i-1];27         g[i]=sqr(s[i]);28     }29     for (int j=1; j
           
            k(q[r],i)) r--;37 q[++r]=i;38 } 39 memcpy(g,f,sizeof(g));40 memset(f,0,sizeof(0));41 }42 printf("%d",m*f[n]-sqr(s[n]));43 return 0;44 }45 46