题目大意：

　　给你一个长度为n的数列，让你分成m段，使得每一段数字和的方差最小。

　　输出最小方差*m*m。

思路：

　　不难想到一个DP。

　　设f[i][k]表示前i个数分成k段，则

　　f[i][k]=std::min(f[i][k],m*sqr(sum[i])-2*sum[n]*sum[i]+f[j][k-1]+2*sum[n]*sum[j]-2*m*sum[i]*sum[j]+m*sqr(sum[j]));

　　答案即为sqr(sum[n])+f[n][m]。

　　复杂度O(n^3)。

　　一开始把方程往奇怪的方向推，最后没弄出来斜率式。

　　实际上如果我们用i和j表示可以被转移的两个状态，那么我们只需要维护一个关于斜率(f[i][!(k&1)]-f[j][!(k&1)]+sqr(sum[i])-sqr(sum[j]))/(sum[i]-sum[j])单调递增的队列。

　　这样就可以优化到O(n^2)。

1 #include
     
       2 #include
      
        3 typedef long long int64; 4 inline int getint() { 5     register char ch; 6     while(!isdigit(ch=getchar())); 7     register int x=ch^'0'; 8     while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0'); 9     return x;10 }11 const int64 inf=0x7ffffffffffffffll;12 const int N=3001;13 int q[N],h,t;14 int64 sum[N],f[N][2];15 inline int64 sqr(const int64 &x) {16     return x*x;17 }18 inline double calc(const int &i,const int &j,const int &k) {19     return double(f[i][!(k&1)]-f[j][!(k&1)]+sqr(sum[i])-sqr(sum[j]))/double(sum[i]-sum[j]);20 }21 int main() {22     const int n=getint(),m=getint();23     for(register int i=1;i<=n;i++) sum[i]=sum[i-1]+getint();24     for(register int i=1;i<=n;i++) f[i][0]=inf;25     for(register int k=1;k<=m;k++) {26         q[h=t=0]=k-1;27         for(register int i=k;i<=n;i++) {28             while(h
       
        <=2*sum[i]) h++;29             f[i][k&1]=f[q[h]][!(k&1)]+sqr(sum[i]-sum[q[h]]);30             while(h
        
         <=calc(q[t],q[t-1],k)) t--;31             q[++t]=i;32         }33     }34     printf("%lld\n",f[n][m&1]*m-sqr(sum[n]));35     return 0;36 }