BZOJ 1010: [HNOI2008]玩具装箱toy(dp+斜率优化)

 要写题解好像很长...不想写(不会写..) BZOJ discuss里讲得挺好的...

------------------------------------------------------------------------------

#include<cstdio>

#include<cstring>

#include<iostream>

#include<algorithm>

 

#define Rep(i,l,r) for(int i=l;i<=r;++i)

 

using namespace std;

 

typedef long long ll;

const int maxn=50000+5;

 

ll sum[maxn];

ll d[maxn];

int q[maxn];

 

#define A(i) (sum[i]+i)

#define B(i) (A(i)+1+l)

#define X(k,j) (d[k]+B(k)*B(k)-d[j]-B(j)*B(j))

#define Y(k,j) (B(k)-B(j))

 

int main()

{

// freopen("test.in","r",stdin);

// freopen("test.out","w",stdout);

int n,l;

scanf("%d%d",&n,&l);

sum[0]=0;

Rep(i,1,n) {

int t; scanf("%d",&t);

sum[i]=sum[i-1]+t;

}

int front=0,rear=0; q[0]=d[0]=0;

Rep(i,1,n) {

while(rear>front && X(q[front+1],q[front])<=Y(q[front+1],q[front])*2*A(i)) ++front;

d[i]=d[q[front]]+(A(i)-B(q[front]))*(A(i)-B(q[front]));

while(rear>front && X(i,q[rear])*Y(q[rear],q[rear-1])*2<=X(q[rear],q[rear-1])*Y(i,q[rear])*2) --rear;

q[++rear]=i;

}

printf("%lld\n",d[n]);

return 0;

}

  

------------------------------------------------------------------------------