[bzoj3675]-[Apio2014]序列分割

题目（BZOJ）
洛谷要输出方案数......在此我就不贴链接了。
 
这题先写dp方程：dp[i][j]表示第i次操作对前j个元素的最大得分。
方程很好写：
dp[i][j]=max(dp[i][j],dp[i-1][k]+sum[k]*(sum[j]-sum[k])), 0<=k<j
而由于这题要开long long，内存只有128M，所以加个滚动数组，ok。
然后就是斜率优化套路了......

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template <class _E> inline void read(_E &e){
	e=0;int ck=1;char ch=getchar();
	while(!isdigit(ch)){if(ch=='-')ck=-1;ch=getchar();}
	while(isdigit(ch)){e=(e<<1)+(e<<3)+(ch^48);ch=getchar();}
	e*=ck;
}
const int N=100050;
int n,K;ll a[N],sum[N],f[N],g[N];
int q[N];
inline double qk(int k,int j){
	return (double)(g[k]-g[j]-sum[k]*sum[k]+sum[j]*sum[j])/(double)(sum[j]-sum[k]);
}
int main(){
	read(n),read(K);
	for (int i=1;i<=n;++i) read(a[i]);
	int nn=0;
	for (int i=1;i<=n;++i) if(a[i])a[++nn]=a[i];
	n=nn;
	for (int i=1;i<=n;++i) sum[i]=sum[i-1]+a[i];
	for (int k=1;k<=K;++k){
		int head=1,tail=0;
		for (int i=k;i<=n;++i){
			while(head<tail&&qk(q[tail-1],q[tail])>qk(q[tail],i-1))tail--;
			q[++tail]=i-1;
			while(head<tail&&qk(q[head],q[head+1])<sum[i])head++;
			f[i]=g[q[head]]+sum[i]*sum[q[head]]-sum[q[head]]*sum[q[head]];
		}
		for (int i=k;i<=n;++i) swap(f[i],g[i]);
	}
	printf("%lld",g[n]);
	return 0;
}