题目大意：
给你一个长度为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<cstdio> 2 #include<cctype> 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<t&&calc(q[h+1],q[h],k)<=2*sum[i]) h++; 29 f[i][k&1]=f[q[h]][!(k&1)]+sqr(sum[i]-sum[q[h]]); 30 while(h<t&&calc(i,q[t],k)<=calc(q[t],q[t-1],k)) t--; 31 q[++t]=i; 32 } 33 } 34 printf("%lld ",f[n][m&1]*m-sqr(sum[n])); 35 return 0; 36 }