Description
Pine开始了从S地到T地的征途。
从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。
Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天中走完。
Pine希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。
帮助Pine求出最小方差是多少。
设方差是v，可以证明，v×m2。
Input
第一行两个数 n、m。
第二行 n 个数，表示 n 段路的长度
Output
一个数，最小方差乘以 m^2 后的值
Sample Input
5 2
1 2 5 8 6
Sample Output
36
HINT
1≤n≤3000,保证从 S 到 T 的总路程不超过 30000
方差公式
\[\frac { \sum_{i=1}^m(x_i-\frac{sum}{m})^2}{m}
\]
\]
再乘上\(m^2\)
\[\sum_{i=1}^m[m\times (x_i-\frac{sum}{m})^2]$$画柿子就是
$$m\times \sum_{i=1}^m x^2 -sum^2\]
由于第二项是确定的，所以只需要最小化第一项
继续拆
\[m\times \sum_{i=1}^na_i^2+2\times m\times\sum _{k=1}^m \sum_{i=x_{kl}}^{x_{kr}-1}\sum_{j=i+1}^{x_{kr}}a_i\times a_j
\]
\]
第一项又变成定值，最小化第二项
用\(s[i]\)表示前缀和，\(d[k]\)表示$$\sum_{i=1}ka_i\times a_j$$
那么表示上个柿子第二项就是$$d[r]-d[l]-(s[r]-s[l])\times s[l]$$
然后就可以斜率优化啦!当决策\(l\)比\(k\)优就是
\[s[i]>\frac{(d_l-s_l^2-f_l)-(d_k-s_k^2-f_k)}{s_k-s_l}
\]
\]
\(f_x\)表示的是转移向的代价
#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#define M 3001
#define X(i,k) (d[i]-s[i]*s[i]-f[k][i])
#define xl(x,y,k) ((double)X(x,k)*1.0-(double)X(y,k)*1.0)/((double)s[y]*1.0-1.0*s[x])
#define LL int
LL i,m,n,j,k,a[M],s[M],f[2][M],d[M],sum,q[2][M],tt,top,tail,head;
int main()
{
scanf("%d%d",&n,&m);
for(i=1;i<=n;i++)
{
scanf("%d",&a[i]);
s[i]=s[i-1]+a[i];
d[i]=d[i-1]+a[i]*s[i-1];
sum+=a[i]*a[i];
}
for(i=1;i<=m;i++)
{
tail=top; head=1;
tt=top=0;
int u=i&1;
for(j=i;j<=n;j++)
{
while(q[!u][head]+1<j && head<tail-1 && xl(q[!u][head+1],q[!u][head],!u)<1.0*s[j]) head+=1;
int x=q[!u][head];
f[u][j]=d[j]-d[x]-(s[j]-s[x])*s[x]+f[!u][x];
while(top>tt+1 && xl(q[u][top],q[u][top-1],u)>xl(j,q[u][top],u)) top-=1;
q[u][++top]=j;
}
}
printf("%d",2*f[m&1][n]*m-s[n]*s[n]+sum*m);
}