记录编号	249321	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016 Round1] 征途	最终得分	100
用户昵称	/k	是否通过	通过
代码语言	C++	运行时间	1.385 s
提交时间	2016-04-12 15:48:02	内存使用	69.46 MiB

#include<iostream>
#include<cstring>
#include<cstdio>
using namespace std;
typedef long long ll;
double f[3010][3010];
double s[3010],xb;
int n,m;
inline double sqr(double x)
{
	return x*x;
}
void g(double *F,double *H,int z,int y,int l,int r)
{
	if(z>y)
	    return;
	int mid=(z+y)>>1;
	int mmid=z;
	//if(z==1&&y==2)
	//    printf("P%d\n",H[0]);
	for(int i=l;i<mid;i++)
	    if(F[mid]>H[i]+sqr(s[mid]-s[i]-xb))
	    {
	//printf("%d\n",s[mid]);
			F[mid]=H[i]+sqr(s[mid]-s[i]-xb);
			mmid=i;
	    }
	g(F,H,z,mid-1,l,mmid);
	g(F,H,mid+1,y,mmid,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("%lf",&s[i]);
	//printf("G");
	for(int i=1;i<=n;i++)
	    s[i]+=s[i-1];
	memset(f,127,sizeof(f));
	//printf("%lf\n",f[0][0]);
	/*double XB=s[n]/m;
	printf("%lf\n",XB);*/
	xb=s[n]/(double)m;
	//printf("%lld\n",xb);
	f[0][0]=0.0;
	for(int i=1;i<=m;i++)
	    g(f[i],f[i-1],1,n,0,n);
		//g(f[i],f[i-1],1,min(i,m),0,min(i-1,m));
	//printf("%lld\n",f[2][1]);
	//printf("%d\n",f[n][1]);
	/*for(int i=1;i<=n;i++)
	{
	    for(int j=1;j<=i;++j)
	    {
			int p=-1;
			for(int k=0;k<i;k++)
			    if(f[i][j]>f[k][j-1]+sqr(s[i]-s[k]-xb))
			    {
					f[i][j]=f[k][j-1]+sqr(s[i]-s[k]-xb);
					p=k;
				}
			//printf("%d\n",p);
		}
		//printf("~~~~~~~~~~~~~~~~~~~~~~~~~~~~\n");
	}*/
	//printf("%lld\n",f[n][1]);
	//printf("%lf\n",f[n][m]);
	f[m][n]/=(double)m;
	f[m][n]*=sqr((double)m);
//	printf("%lld\n",f[n][m]);
//	double p=(double)f[n][m]/(double)m;//*(double)m*(double)m;
	printf("%.lf",f[m][n]);
	/*f[n][m]*=m*m;
	getchar();
	getchar();*/
}