[文章目录]
Description
从S地到T地的路可以划分成n段，相邻两段路的分界点设有休息站。
Pine计划用m天到达T地。除第m天外，每一天晚上Pine都必须在休息站过夜。所以，一段路必须在同一天中走完。
Pine希望每一天走的路长度尽可能相近，所以他希望每一天走的路的长度的方差尽可能小。
帮助Pine求出最小方差是多少。
设方差是v，可以证明，v×m^2是一个整数。为了避免精度误差，输出结果时输出v×m^2。n,m<=3000 dis<=30000
首先：方差=平方（和）的均值-均值的平方。推一推就好了。那么最小化平方和即可。
dp[i][j] 走了i段路，歇了j次的最小平方和，得：
dp[i][j]=min(dp[k][j-1]+(s[i]-s[k])^2)
对于第二维维护队列进行斜率优化即可。O(nm)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int n,m,q[3100],now;
ll s[3100],dp[3100][3100];
ll k(int x) {return -2ll*s[x];}
ll b(int x) {return dp[now][x]+s[x]*s[x];}
int main()
{
scanf("%d%d",&n,&m);
int x;
for(int i=1;i<=n;++i)
{
scanf("%d",&x);
s[i]=s[i-1]+x;
}
memset(dp,0x3f,sizeof dp);
for(int j=1;j<=n;++j) dp[1][j]=s[j]*s[j];
int l,r;
for(int i=2;i<=m;++i)
{
l=1; r=0; now=i-1;
for(int j=1;j<=n;++j)
{
while(l<r && k(q[l])*s[j]+b(q[l]) >= k(q[l+1])*s[j]+b(q[l+1])) l++;
dp[i][j]=k(q[l])*s[j]+b(q[l])+s[j]*s[j];
while(l<r && (b(q[r])-b(j))*(k(q[r])-k(q[r-1])) <= (b(q[r-1])-b(q[r]))*(k(j)-k(q[r])) ) --r;
q[++r]=j;
}
}
printf("%lld",dp[m][n]*m-s[n]*s[n]);
return 0;
}