Bakser's Blog

我是逗比。

bzoj1096 斜率优化

| Comments

GTY的题解,我懒不写

bzoj1096
#include<cstdio>
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
#define N 1001000
struct hh
{
    LL x,y;
    hh(LL _x=0,LL _y=0):x(_x),y(_y){}
}q[N];
inline LL cross(const hh &o,const hh &a,const hh &b)
{
    return (a.x-o.x)*(b.y-o.y)-(b.x-o.x)*(a.y-o.y);
}
LL n,x[N],p[N],sp[N],c[N],f[N],head,tail;
inline LL calc(int i,const hh &t)
{
    return t.y-x[i]*t.x+x[i]*p[i]-sp[i]+c[i];
}
int main()
{
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%lld%lld%lld",x+i,p+i,c+i);
        sp[i]=sp[i-1]+p[i]*x[i];
        p[i]+=p[i-1];
    }
    q[tail++]=hh(0,0);
    for(int i=1;i<=n;i++)
    {
        while(head+1<tail&&calc(i,q[head])>=calc(i,q[head+1]))head++;
        f[i]=calc(i,q[head]);
        hh t(p[i],f[i]+sp[i]);
        while(head+1<tail&&cross(q[tail-2],q[tail-1],t)<=0)tail--;
        q[tail++]=t;
    }
    printf("%lld",f[n]);
    return 0;
}

Comments

comments powered by Disqus