BZOJ2726: [SDOI2012]任务安排-白红宇

BZOJ2726: [SDOI2012]任务安排

阅读量：4548 次

发布时间：2019-06-08

本文共 1454 字，大约阅读时间需要 4 分钟。

题目：http://www.lydsy.com/JudgeOnline/problem.php?id=2726

倒着做，前面的点对后面的点都是有贡献的。 f[i]=min(f[j]+cost[i]*(T[i]-T[j]+S)) (j>i)

然后。。。。时间可以是负数的。（所以看起来好好的单调队列+斜率优化就变成了动态凸包。。x坐标并不是有序的。。

用cdq分治处理。。

（看起来是要逆序维护下凸包的。但是我比较蠢于是把序列翻转了一下这样就变成了正着做下凸包辣。。

然后时间是负数的话，不等号的方向要改变。

（虽然我在写的时候脑子一团浆糊。。但是感觉写出来的代码还不会太乱吧。。

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          #include
           
            #define rep(i,l,r) for (int i=l;i<=r;i++)#define down(i,l,r) for (int i=l;i>=r;i--)#define clr(x,y) memset(x,y,sizeof(x))#define maxn 300500#define inf int(1e9)#define ll long longusing namespace std;struct data{ int x,k,id;ll y;}a[maxn],s[maxn],t[maxn];int n,S;ll f[maxn],bin[69];int cross(data a,data b,data c){ int x1=b.x-a.x,x2=c.x-a.x; ll y1=b.y-a.y,y2=c.y-a.y; if ((x1<0)^(x2<0)) return y1*x2<=y2*x1; else return x1*y2-x2*y1<=0;}bool jud(data a,data b,int k){ ll x=b.x-a.x,y=b.y-a.y; if (x<0) return y>x*k; else return y
            
             1&&cross(s[top-1],s[top],a[i])) top--; s[++top]=a[i]; } int j=1; rep(i,mid+1,r){ while (j
             
              r)) t[i]=a[l1++]; else t[i]=a[l2++]; rep(i,l,r) a[i]=t[i];}int main(){ n=read(); S=read(); rep(i,1,n) a[i].x=read(),a[i].k=read(); down(i,n,1) a[i].x+=a[i+1].x,a[i].k+=a[i+1].k; rep(i,1,n/2) swap(a[i],a[n-i+1]); rep(i,1,n) f[i]=1LL*a[i].k*(a[i].x+S),a[i].id=i; f[0]=0; cdq(1,n); printf("%lld\n",f[n]); return 0;}