记录编号	384554	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016 Round1] 征途	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	0.944 s
提交时间	2017-03-18 17:52:25	内存使用	69.49 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef long double db;
const int N=3010;
int n,m,k,d[N],q[N],hd,tl;
ll dp[N][N],s[N];db kl[N];
//dp[i][j]表示到过前i段,分j段的最小贡献 
ll sqr(ll x){return x*x;}
db K(int i,int j){
	return db(dp[i][k-1]-dp[j][k-1])/(s[i]-s[j])+m*m*(s[i]+s[j]);
}
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",&d[i]),s[i]=s[i-1]+d[i];
	for (int i=0;i<=n;i++)
	for (int j=0;j<=m;j++)
		dp[i][j]=1e16;
	dp[0][0]=0;
	for (k=1;k<=m;k++){
		q[hd=tl=1]=0;
		for (int i=1;i<=n;i++){
			for (;hd<tl&&kl[tl]>K(q[tl],i);tl--);
			q[++tl]=i;kl[tl]=K(q[tl-1],q[tl]);
			for (;hd<tl&&kl[hd+1]<2*m*(m*s[i]-s[n]);hd++);
			dp[i][k]=dp[q[hd]][k-1]+sqr(m*(s[i]-s[q[hd]])-s[n]);
		}
	}
	printf("%lld\n",dp[n][m]/m);
	return 0;
}