[APIO2010]特别行動隊（斜率優化dp）

【題解】

設s[i]=x[1]+x[2]+……+x[i]

則：f[0]=0

    f[i]=max{ f[j]+zdl(s[i]-s[j]) } ( i>0 , 0<=j<i , zdl(x)=a*x*x+b*x+c )

若 j不比k差 

則：f[j]+a*(s[i]-s[j])^2+b*(s[i]-s[j])+c >= f[k]+a*(s[i]-s[k])^2+b*(s[i]-s[k])+c

整理得：     f[j]+a*s[j]^2-f[k]-a*s[k]^2 >= (2*a*s[i]+b)*(s[j]-s[k])            設t[i]=f[i]+a*s[i]^2, mi=2*a*s[i]+b

則：                            t[j]-t[k]>=m*(s[j]-s[k])                        s[i]單調遞增 

∴ j<k時，K(j,k)<=mi (斜率小，前優)

   k<j時，K(j,k)>mi  (斜率大，後優)

若 j<k<l，且 K(j,k)<=K(k,l)

則總有：j優于k(K(j,k)<=mi) 或 l優于k(mi<K(j,k)<=K(k,l))，應删去k

是以隊列中任意一段j-k-l均上凸 

若j,k為目前隊列前兩位，且 K(j,k)>=mi(k比j優)

∵ m單調遞減 

∴ 對于任意t>i，都滿足 K(j,k)>=mt (k總比j優)

此時可删去隊首 

【代碼】

#include<stdio.h>
#include<stdlib.h>
typedef long long LL;
LL s[1000005],f[1000005],y[1000005],q[1000005];
double K(int i,int j)
{
	return (double)(y[i]-y[j])/(double)(s[i]-s[j]);
}
int main()
{
	double m;
	LL a,b,c;
	int n,i,j,head=0,tail=1;
	scanf("%d%lld%lld%lld",&n,&a,&b,&c);
	for(i=1;i<=n;i++)
	{
		scanf("%lld",&s[i]);
		s[i]+=s[i-1];
	}
	for(i=1;i<=n;i++)
	{
		m=(double)(2*a*s[i]+b);
		while(tail-head>=2&&K(q[head],q[head+1])>m) head++;
		f[i]=f[q[head]]+a*(s[i]-s[q[head]])*(s[i]-s[q[head]])+b*(s[i]-s[q[head]])+c;
		y[i]=f[i]+a*s[i]*s[i];
		while( tail-head>=2 && K( q[tail-2] , q[tail-1] ) < K( q[tail-1] , i ) ) tail--;
		q[tail++]=i;
	}
	printf("%lld",f[n]);
	return 0;
}