设x[i]为第i天走的路程，s为路程总和，则:
ans=[(s/m-x[1])^2+(s/m-x[2])^2+(s/m-x[3])^2+...+(s/m-x[m])^2]*m
=[(s-x[1]*m)^2+(s-x[2]*m)^2+(s-x[3]*m)^2]+...+(s-x[m]*m)^2)]/m
=s^2+m*(x[1]^2+x[2]^2+x[3]^2+...+x[m]^2)-2*(x[1]+x[2]+x[3]+...+x[m])*s
=m*(x[1]^2+x[2]^2+x[3]^2+...+x[m]^2)-s^2
由于m,s不变，问题可以转化为将一个长为n的序列划分成m段，求最小平方和。
令f[i][j]为将长为j的序列划分成i段的最小平方和，则
f[i][j]=min(f[i][k]+(sum[j]-sum[k])^2)，0<k<j
很明显的斜率优化。
斜率优化过程如下：
设p<k<j，在求f[i][j]时k比p优，于是可得如下方程：
f[i-1][k]+(sum[j]-sum[k])^2<f[i-1][p]+(sum[j]-sum[p])^2
f[i-1][k]+sum[k]^2-(f[i-1][p]+sum[p]^2)<2*(sum[k]-sum[p])*sum[j]
(f[i-1][k]+sum[k]^2-(f[i-1][p]+sum[p]^2))/(2*sum[k]-2*sum[p])<sum[j]
如果令y[i-1][t]=f[i-1][t]+sum[t]^2，x[i-1][t]=2*sum[t]，
则原式可化为：(y[i-1][k]-y[i-1][p])/(x[i-1][k]-x[i-1][p])<sum[j]，不就是线段kp的斜率小于sum[j]吗？
令g[i][j](i>j)为线段ij的斜率。
于是在求f[i]时维护一个序列，满足对任意j(j>2)，g[j][j-1]>g[j-1][j-2]，则f[i][j]的最优值就从序列中斜率小于sum[j]的序号最大的线段的右端点转移。
时间复杂度从O(n*n*m)降到O(n*m)
代码：
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define ll long long
ll i,j,k,n,m,f[][],x[],y[][],sum[],s,l,r,q[];
int main()
{
scanf("%d%d",&n,&m);
for(i=;i<=n;i++)scanf("%lld",&sum[i]),s+=sum[i],sum[i]+=sum[i-],x[i]=sum[i]<<,f[][i]=sum[i]*sum[i],y[][i]=f[][i]<<;
for(i=;i<=m;i++){
l=r=;
for(j=;j<=n;j++){
while(l<r&&y[i-][q[l+]]-y[i-][q[l]]<=sum[j]*(x[q[l+]]-x[q[l]]))l++;
f[i][j]=f[i-][q[l]]+(sum[j]-sum[q[l]])*(sum[j]-sum[q[l]]);
y[i][j]=f[i][j]+sum[j]*sum[j];
while(l<r&&(x[q[r]]-x[q[r-]])*(y[i-][j]-y[i-][q[r-]])<=(x[j]-x[q[r-]])*(y[i-][q[r]]-y[i-][q[r-]]))r--;
q[++r]=j;
}
}
printf("%lld\n",f[m][n]*m-s*s);
return ;
}
bzoj4518