题目链接

斜率优化 不说了 网上很多 这的比较详细->Click Here or Here

//1700kb	60ms

#include<cstdio>

#include<cctype>

//#define gc() getchar()

#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

typedef long long LL;

const int N=5e4+5,MAXIN=1e5;

int n,C,S[N],q[N];

char IN[MAXIN],*SS=IN,*TT=IN;

LL f[N];

inline int read()

{

	int now=0,f=1;register char c=gc();

	for(;!isdigit(c);c=gc()) if(c=='-') f=-1;

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now*f;

}

inline LL Squ(LL x){

	return x*x;

}

inline LL X(int j,int k){

	return (S[j]-S[k])<<1;

}

inline LL Y(int j,int k){

	return f[j]+Squ(S[j]+C)-(f[k]+Squ(S[k]+C));

}

int main()

{

	n=read(),C=read()+1;

	for(int i=1;i<=n;++i) S[i]=S[i-1]+read()+1;

//	for(int i=1;i<=n;++i) S[i]+=i;

	int h=1,t=1; q[1]=0;

	for(int i=1;i<=n;++i)

	{

		while(h<t && Y(q[h+1],q[h])<=S[i]*X(q[h+1],q[h])) ++h;

		f[i]=f[q[h]]+Squ(S[i]-S[q[h]]-C);

		while(h<t && Y(i,q[t])*X(q[t],q[t-1])<=Y(q[t],q[t-1])*X(i,q[t])) --t;

		q[++t]=i;

	}

	printf("%lld",f[n]);

	return 0;

}

由决策单调，单调队列写法：\(\mathcal O(n\log n)\)

//2288kb	140ms

#include <cstdio>

#include <cctype>

#include <algorithm>

//#define gc() getchar()

#define MAXIN 100000

#define gc() (SS==TT&&(TT=(SS=IN)+fread(IN,1,MAXIN,stdin),SS==TT)?EOF:*SS++)

typedef long long LL;

const int N=50005;

int n,L;

LL sum[N],f[N];

char IN[MAXIN],*SS=IN,*TT=IN;

struct Node{

	int l,r,pos;//pos是区间[l,r]的最优转移点

}q[N];

inline int read()

{

	int now=0;register char c=gc();

	for(;!isdigit(c);c=gc());

	for(;isdigit(c);now=now*10+c-'0',c=gc());

	return now;

}

inline LL Squ(LL x){

	return x*x;

}

inline LL Cost(int i,int p){//在i之前，分割p处

	return f[p]+Squ((LL)(i-p-1+sum[i]-sum[p]-L));

}

int Find(Node t,int x)

{

	int l=t.l, r=t.r, mid;

	while(l<=r)

		if(mid=l+r>>1, Cost(mid,x)<Cost(mid,t.pos)) r=mid-1;

		else l=mid+1;

	return l;

}

int main()

{

	n=read(), L=read();

	for(int i=1; i<=n; ++i) sum[i]=sum[i-1]+read();

	int h=1,t=1; q[1]=(Node){0,n,0};

	for(int i=1; i<=n; ++i)

	{

		if(i>q[h].r) ++h;

		f[i]=Cost(i,q[h].pos);

		if(Cost(n,i)<Cost(n,q[t].pos))//为什么要拿n比？？不解。

		{

			while(h<=t && Cost(q[t].l,i)<Cost(q[t].l,q[t].pos)) --t;//队尾区间的l用i都比pos更优了，而决策点是单调的，所以[l,r]肯定都要不选pos而选i了

			if(h>t) q[++t]=(Node){i,n,i};

			else

			{

				int Pos=Find(q[t],i);

				q[t].r=Pos-1, q[++t]=(Node){Pos,n,i};

			}

		}

	}

	printf("%lld",f[n]);

	return 0;

}