BZOJ.1010.[HNOI2008]玩具装箱toy(DP 斜率优化/单调队列 决策单调性)

题目链接
斜率优化 不说了 网上很多 这的比较详细->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(nlog 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;
}