记录编号	249177	评测结果	AAAAAAAAAA
题目名称	[SDOI 2016 Round1] 征途	最终得分	100
用户昵称	_Horizon	是否通过	通过
代码语言	C++	运行时间	1.275 s
提交时间	2016-04-12 11:36:07	内存使用	69.48 MiB

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#define maxn 3010
using namespace std;
 
int n, m, a[maxn];
 
long long dp[maxn][maxn];
long long s[maxn];
 
int que[maxn], head, tail;
 
#define sqr(x) (x) * (x)
 
long double getK(int j, int k, int tp){
	return (long double)(dp[tp][k] - dp[tp][j] + sqr(s[k]) - sqr(s[j])) / 2.0 / (s[k] - s[j]);
}
 
void trans(int j){
	head = tail = 1;
	que[1] = 0;
	for(int i = 1; i <= n; i ++){
		while(head < tail && s[i] >= getK(que[head], que[head+1], j-1))
		    head ++;
		dp[j][i] = dp[j-1][que[head]] + sqr(s[i] - s[que[head]]);
		while(head < tail && getK(que[tail-1], que[tail], j-1) > getK(que[tail], i, j-1))
		    tail --;
		que[++ tail] = i;
	}
}
 
int main(){
	freopen("menci_journey.in", "r", stdin);
	freopen("menci_journey.out", "w", stdout);
	scanf("%d%d", &n, &m);
	memset(dp, 0x7f, sizeof dp);
	dp[0][0] = 0;
	for(int i = 1; i <= n; i ++)
	    scanf("%d", &a[i]), s[i] = s[i-1] + a[i];
	for(int j = 1; j <= m; j ++)
	    trans(j);
	printf("%lld\n", dp[m][n] * m - sqr(s[n]));
	return 0;
}