[SDOI2016]征途

又来水博客了
[SDOI2016]征途
推一下柿子就会发现，我们要求最小值的部分是将整个序列分为来m段，然后每段和的平方相加最小。

\(f[i][j]=f[k][j-1]+(s[i]-s[k])^2\),然后用滚动数组优化一下。
\(g[i]=f[k]+s[i]^2-2s[i]s[k]+s[k]^2\)
\(f[k]+s[k]^2=g[i]-s[i]^2+2s[i]s[k]\)
将决策看作(\(2s[k]\),\(f[k]+s[k]^2\))即可。

#include<cstdio>
#include<algorithm>
#include<cstring>
#define fo(i,a,b) for (int (i)=(a);(i)<=(b);(i)++)
using namespace std;
typedef long long ll;
const int N=3005;
ll f[N],g[N],s[N],z,ans;
int h,t,q[N],n,m;
ll Y(int x){
	return f[x]+s[x]*s[x];
}
ll X(int x){
	return 2*s[x];
}
ll down(int a,int b){
	return X(a)-X(b);
}
ll up(int a,int b){
	return Y(a)-Y(b);
}
ll sqr(ll x){
	return x*x;
}
int main(){
//	freopen("data.in","r",stdin);
	scanf("%d %d",&n,&m);
	fo(i,1,n) {
		scanf("%lld",&z);
		s[i]=s[i-1]+z;
	}
	
	memset(f,0x3f,sizeof(f));
	
	f[0]=0;
	fo(j,1,m){

		h=t=1; 
		memset(q,0,sizeof(q));
		fo(i,1,n) {
			while (h<t && up(q[h+1],q[h]) <= s[i]*down(q[h+1],q[h]) ) h++;
			g[i]=f[q[h]]+sqr(s[i]-s[q[h]]);
			while (h<t && up(i,q[t])*down(q[t],q[t-1]) <=down(i,q[t])*up(q[t],q[t-1]) ) t--;
			q[++t]=i;
		}
		
		fo(i,1,n) f[i]=g[i];
	}
	
	ans=m*f[n]-sqr(s[n]);
	
	printf("%lld\n",ans);
	return 0;
}