记录编号	250791	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016 Round1] 征途	最终得分	100
用户昵称	神利·代目	是否通过	通过
代码语言	C++	运行时间	0.370 s
提交时间	2016-04-15 21:44:47	内存使用	69.43 MiB

#include<stdio.h>
#define ll long long
int n,m,a[3010],sum[3010];
double x,f[3010][3010];
double sqr(double x){return x*x;}
inline void sol(double *f1,double *f2,int l,int r,int L,int R){
	if(l>r)return;
	double t=1e20;int k;
	int mid=l+r>>1;
	for(int i=L;i<=R;++i){
		double p=f1[i]+sqr(sum[mid]-sum[i]-x);
		if(p<t)t=p,k=i;
	}
	f2[mid]=t;
	sol(f1,f2,l,mid-1,L,k);
	sol(f1,f2,mid+1,r,k,R);
}
int main(){
	freopen("menci_journey.in","r",stdin);
	freopen("menci_journey.out","w",stdout);
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i)scanf("%d",&a[i]),sum[i]=sum[i-1]+a[i];
	x=(double)sum[n]/m;
	for(int i=0;i<=m;++i)
	    for(int j=0;j<=n;++j)
	        f[i][j]=1e20;
	f[0][0]=0;
	for(int i=1;i<=m;++i)
	    sol(f[i-1],f[i],1,n,i-1,n);
	printf("%lld",(ll)(f[m][n]*m+0.5));
	//while(1);
}