AC日记——[HNOI2008]玩具装箱toy bzoj 1010

1010

思路：

　　斜率优化DP；

　　跪烂大佬

代码：

#include <bits/stdc++.h>

using namespace std;

#define maxn 50005

#define ll long long

ll que[maxn],sum[maxn],dp[maxn],n,l,ai[maxn],a;

inline void in(ll &now)

{

    char Cget=getchar();now=;

    while(Cget>''||Cget<'')Cget=getchar();

    while(Cget>=''&&Cget<='')

    {

        now=now*+Cget-'';

        Cget=getchar();

    }

}

ll G(ll now)

{

    return sum[now]+now;

}

ll Y(ll x,ll y)

{

    return dp[x]+pow(G(x)+a,)-dp[y]-pow(G(y)+a,);

}

ll X(ll x,ll y)

{

    return *(G(x)-G(y));

}

int main()

{

    in(n),in(l),a=l+;ll h=,tail=;

    for(ll i=;i<=n;i++) in(ai[i]),sum[i]=sum[i-]+ai[i];

    for(ll i=;i<=n;i++)

    {

        while(h<tail&&Y(que[h+],que[h])<=G(i)*X(que[h+],que[h])) ++h;

        dp[i]=dp[que[h]]+(G(i)-G(que[h])-a)*(G(i)-G(que[h])-a);

        while(h<tail&&Y(i,que[tail])*X(que[tail],que[tail-])<=Y(que[tail],que[tail-])*X(i,que[tail])) --tail;

        que[++tail]=i;

    }

    cout<<dp[n];

    return ;

}