题目描述
Pine开始了从S地到T地的征途。
从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。
Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天中走完。
Pine希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。
帮助Pine求出最小方差是多少。
设方差是v，可以证明，v\times m^2v×m2是一个整数。为了避免精度误差，输出结果时输出v\times m^2v×m2。
输入格式
第一行两个数 n、m。
第二行 n 个数，表示 n 段路的长度
输出格式
一个数，最小方差乘以 m^2m2 后的值
输入输出样例
输入 #1复制
5 2
1 2 5 8 6
输出 #1复制
36
说明/提示
对于 30% 的数据，1≤n≤10
对于 60% 的数据，1≤n≤100
对于 100% 的数据，1≤n≤3000
保证从 S 到 T 的总路程不超过 30000 。
题解：题目意思是n段路每段路有一个长度，分m次走完，让你求这m次的方差乘以m^2的最小值。
参考代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=;
int n,m,q[maxn];
ll f[maxn],g[maxn],sum[maxn],val;
inline ll X(int i){return sum[i];}
inline ll Y(int i){return (g[i]+sum[i]*sum[i]);}
inline double slope(int x,int y){return 1.0*(Y(y)-Y(x))/(X(y)-X(x));} int main()
{
scanf("%d%d",&n,&m); sum[]=;
for(int i=;i<=n;++i)
{
scanf("%lld",&val);
sum[i]=sum[i-]+val;
g[i]=sum[i]*sum[i];
} for(int i=;i<m;++i)//m days
{
int l=,r=;q[]=i;
for(int j=i+;j<=n;++j)// n roads
{
while(l<r&&slope(q[l],q[l+])<2.0*sum[j])++l;
f[j]=g[q[l]]+(sum[j]-sum[q[l]])*(sum[j]-sum[q[l]]);
while(l<r&&slope(q[r-],q[r])>slope(q[r-],j)) --r;
q[++r]=j;
}
for(int j=;j<=n;++j) g[j]=f[j];
}
printf("%lld\n",m*f[n]-sum[n]*sum[n]); return ;
}