题目
题目描述
Pine开始了从S地到T地的征途。从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。
Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天中走完。
Pine希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。帮助Pine求出最小方差是多少。
设方差是v，可以证明，$v\times m^2$是一个整数。
为了避免精度误差，输出结果时输出$v\times m^2$。
输入输出格式
输入格式：
第一行两个数 n、m。
第二行 n 个数，表示 n 段路的长度
输出格式：
一个数，最小方差乘以$m^2$后的值
输入输出样例
输入样例#1：
5 2
1 2 5 8 6
输出样例#1：
36
说明
对于$30\%$的数据，$1\leq n\leq 10$
对于$60\%$的数据，$1\leq n\leq 100$
对于$100\%$的数据，$1\leq n\leq 3000$
保证从 S 到 T 的总路程不超过 30000 。
题解
求方差…先搞式子耐心看完
已知： $s^{2}=\frac {(\overline v-v1)^{2}+(\overline v-v2)^{2}+…+(\overline v-vm)^{2}}{m}$
然后：$s^{2}=\frac {(\frac {\sum_{i=1}^{m}vi}{m} -v1)^{2}+(\frac {\sum_{i=1}^{m}vi}{m} -v2)^{2}+…+(\frac {\sum_{i=1}^{m}vi}{m} -vm)^{2}}{m}$
展开：$s^{2}=\frac {m\frac {(\sum_{i=1}^{m}vi)^{2}}{m^{2}}-2\frac {(\sum_{i=1}^{m}vi)}{m}(v1+v2+…+vm)+(v1^{2}+v2^{2}+…+vm^{2})}{m}$
然后可化为： $s^{2}=\frac {\frac {(\sum_{i=1}^{m}vi)^{2}}{m}-2\frac {(\sum_{i=1}^{m}vi)^{2}}{m}+(v1^{2}+v2^{2}+…+vm^{2})}{m}$
然后真TM麻烦：
$s^{2}=-\frac {(\sum_{i=1}^{m}vi)^{2}}{m^{2}}+\frac {(v1^{2}+v2^{2}+…+vm^{2})}{m}$
还要$\times m^2$ $s^{2}m^{2}=-(\sum_{i=1}^{m}vi)^{2}+m(v1^{2}+v2^{2}+…+vm^{2})$
这样就好啦，你会发现式子右边第一项是个定值，而第二项我们可以用前缀和搞搞
用$f_{i,l}$表示前$i$段分为$l$天走的最小方差（这里也是平方了因为最后处理成方差了QAQ）
即有：$f_{i,l}=min(f_{i,l},f_{j,l-1}+(sum_i-sum_j)^{2})(0\le j<i)$（$m$可以最后乘上）
然后$80$分到手好我已经满足了
可以发现这个式子可以用斜率优化搞，即可以这么化：
$f_{i,l}+2sum_isum_j=f_{j,l-1}+{sum_i}^{2}+{sum_j}^{2}$
然后就是斜率优化套路了套路我还WA那么多次
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# define LL long long
using namespace std;
const int MAX=3e3+1;
int n,m;
int qu[MAX];
LL sum[MAX],f[MAX],g[MAX];
int read()
{
int x=0;
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
double X(int i)
{
return sum[i];
}
double Y(int i)
{
return g[i]+sum[i]*sum[i];
}
double look(int x,int y)
{
return (Y(x)-Y(y))/(X(x)-X(y));
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;++i)
sum[i]=sum[i-1]+read(),g[i]=sum[i]*sum[i];
for(int l=1;l<m;++l)
{
int he=1,ta=1;
qu[1]=l;
for(int i=l+1;i<=n;++i)
{
while(he<ta&&look(qu[he],qu[he+1])<2*sum[i]) ++he;
int tt=qu[he];
f[i]=g[tt]+(sum[i]-sum[tt])*(sum[i]-sum[tt]);
while(he<ta&&look(qu[ta],qu[ta-1])>look(qu[ta],i)) --ta;
qu[++ta]=i;
}
for(int i=1;i<=n;i++)
g[i]=f[i];
}
printf("%lld",-sum[n]*sum[n]+m*f[n]);
return 0;
}
