玩具装箱TOY[斜率优化]

玩具装箱TOY[斜率优化]

​​传送门​​

第一次自己推斜率优化,好高兴

对于区间的长度,s[i]表示前缀和在加上i

也就是

首先,考虑暴力的DP

拆开

整理成如下形式

也就是

最小值维护下凸包

#include#define y(A) (f[A]+s[A]*s[A]+s[A])#define k(A) (2*s[A]-2*L)#define x(A) (s[A])#define N 50005#define inf 1000000000000000#define LL long longusing namespace std;LL n,L,s[N],f[N],q[N];double K(int i,int j){return 1.0*(y(j)-y(i))/(x(j)-x(i));}int main(){ scanf("%lld%lld",&n,&L); for(int i=1;i<=n;i++){ LL x; scanf("%lld",&x); s[i]=s[i-1]+x; } for(int i=1;i<=n;i++) s[i]+=i; int l=1,r=1; for(int i=1;i<=n;i++){ while(l

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。