斜率优化。。因为要求方差乘m^2...也就是每段距离与平均值的平方和再乘m。
f[i][j]表示i天后，走了j段的最小平方和。
求出最小平方和再乘个m就行了= =
需要注意，是可以停留在原地的。。。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<cstdlib> 5 #include<cmath> 6 #define d double 7 #define ll long long 8 using namespace std; 9 const int maxn=3023; 10 int i,j,k,n,m,now,pre,l,r; 11 ll pr[maxn],V[maxn]; 12 int dl[maxn]; 13 d f[2][maxn],v1[maxn]; 14 15 16 int ra,fh;char rx; 17 inline int read() { 18 rx=getchar(),ra=0,fh=1; 19 while((rx<'0'||rx>'9')&&rx!='-')rx=getchar(); 20 if(rx=='-')fh=-1,rx=getchar(); 21 while(rx>='0'&&rx<='9')ra*=10,ra+=rx-48,rx=getchar();return ra*fh; 22 } 23 inline d xl(int k1,int k2){//k1<k2 24 return (d)(f[pre][k2]-f[pre][k1]+V[k2]-V[k1])/(pr[k2]-pr[k1]); 25 } 26 inline d sqr(d x){return x*x;} 27 int main(){ 28 n=read(),m=read(); 29 for(i=1;i<=n;i++)pr[i]=pr[i-1]+read(),V[i]=pr[i]*pr[i]; 30 d avg=(d)pr[n]/m; 31 for(i=0;i<=n;i++)f[0][i]=sqr(pr[i]-avg),v1[i]=(pr[i]-avg); 32 now=1,pre=0; 33 for(i=2;i<=m;i++,swap(now,pre)){ 34 l=1,r=0; 35 for(j=0;j<=n;j++){ 36 while(l<r&&xl(dl[r-1],dl[r])>=xl(dl[r],j))r--; 37 dl[++r]=j; 38 while(l<r&&2*v1[j]>=xl(dl[l],dl[l+1]))l++; 39 f[now][j]=f[pre][dl[l]]+sqr(v1[j]-pr[dl[l]]); 40 } 41 } 42 printf("%lld ",(ll)(f[pre][n]*m+0.5)); 43 return 0; 44 }