P3628 [APIO2010]特别行动队

思路：斜率优化(DP)

提交：(1)次

题解：

转移方程：(f[i]=max(f[j]+A*(s[i]-s[j])^2+B*(s[i]-s[j])+C))
写成可以斜率优化的式子：(f[j]+A*s[j]^2-B*s[j]+C=2*A*s[i]*s[j]+f[i]-A*s[j]^2-B*s[i])
然后求(f[i])最大值，于是维护上凸包；横坐标单调增，斜率单调减，所以直接上单调队列即可。

#include<cstdio>
#include<iostream>
#define R register int
#define ll long long
using namespace std;
namespace Luitaryi {
template<class I> inline I g(I& x) { x=0;
	register I f=1; register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;
	do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*=f;
} const int N=1e6+10;
int n,A,B,C,h=0,t=0,q[N];
ll s[N],f[N];
inline double X(int i) {return s[i];}
inline double Y(int i) {return f[i]+A*s[i]*s[i]-B*s[i]+C;}
inline double K(int i,int j) {return (Y(i)-Y(j))/(X(i)-X(j));}
inline void main() {
	g(n),g(A),g(B),g(C); for(R i=1;i<=n;++i) g(s[i]),s[i]+=s[i-1];
	for(R i=1;i<=n;++i) {
		while(h<t&&K(q[h],q[h+1])>=2.0*A*s[i]) ++h;
		f[i]=f[q[h]]+A*(s[i]-s[q[h]])*(s[i]-s[q[h]])+B*(s[i]-s[q[h]])+C;
		while(h<t&&K(q[t],i)>=K(q[t-1],i)) --t; q[++t]=i; 
	} printf("%lld
",f[n]);
}
} signed main() {Luitaryi::main(); return 0;}

2019.08.16
84