【BZOJ 4518】[Sdoi2016] 征途

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4518
数据生成器：http://paste.ubuntu.com/23249800/

做过玩具装箱的童鞋，看一眼就知道是斜率DP吧？

#include<bits/stdc++.h>
#define pow(x) ((x)*(x))
#define LL long long
using namespace std;

const int N = 3000+9;
const LL INF = 1e16;

LL f[N][N];
short n,m,l[N],sum,que[N][N],t1[N],t2[N];
double slope[N][N],Y[N][N];

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int main(){ 
	n = read(); m = read();
	for (int i=1;i<=n;i++) sum += (l[i] = read()), l[i] += l[i-1];
	for (int i=0;i<m;i++) t1[i] = 1, f[n][i] = -1; t2[0] = 1;
	for (int i=1;i<=n;i++) for (int j=m-1;~j;j--) {
		if (t1[j]>t2[j]) continue; double tmp = 2.0*m*((double)m*l[i]-sum);
		while (t2[j] > t1[j] && slope[j][t1[j]] <= tmp) t1[j]++; 
		f[i][j+1] = f[que[j][t1[j]]][j] + pow(sum-(LL)m*(l[i]-l[que[j][t1[j]]]));
		tmp = f[i][j+1] + pow((double)m*l[i]); 
		while (t1[j+1] < t2[j+1] && ((tmp-Y[j+1][t2[j+1]])/(l[i]-l[que[j+1][t2[j+1]]]) <= slope[j+1][t2[j+1]-1])) t2[j+1]--;
		if (t1[j+1] <= t2[j+1]) slope[j+1][t2[j+1]] = (tmp-Y[j+1][t2[j+1]])/(l[i]-l[que[j+1][t2[j+1]]]); 
		t2[j+1]++; que[j+1][t2[j+1]] = i; Y[j+1][t2[j+1]] = tmp; 		
	} LL vout = INF;
	for (int i=1;i<=m;i++) if (~f[n][i]) vout = min(vout,f[n][i]+(LL)(m-i)*pow(sum));
	printf("%lld\n",vout/m); return 0;
}

然而再zgs的OJ上莫名其妙RE了两个点？
奥妙重重……..