P5785 [SDOI2012]任务安排

介绍

这个题我们分析一波P5785 [SDOI2012]任务安排

首先这个s很讨厌，不过我们可以把每一个批次的s的影响扔到后面去，对后面的产生而不是前面，然后写出dp方程

$f_i=f_j+s\times (sum_n-sumc_j)+sumt_i\times(sumc_i-sumc_j)$

然后把只带 $i$ 的放到一边。

$f_i-s\times sumc_n-sumti\times sumc=f_j+sumc_j\times (s+sumc_i) $

按照斜率优化的套路，只有i的是b，只有j的是y，剩下的i和常数是k，j是b

斜率优化就出来了。

但是有一个问题出现了，这里的k一定是正数吗？不一定，

所以我们不得不把整个凸包存下来，使用的时候进行二分查找。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<algorithm>
using namespace std;
#define int long long
template<class T>
void read(T &now){
    now=0;
    char c=getchar();
    int f=1;
    while((!isdigit(c))){
        if(c=='-') f=-1;
    //  cout<<isdigit(c)<<" "<<c<<" ";
        c=getchar();
    }
    while(isdigit(c)){
        now=(now<<1)+(now<<3)+c-'0';
        c=getchar();
    }
    now*=f;
}
int n;
int s;
int t[300006];
int c[300006];
int st[300006];
int sc[300006];
int ta;int he=1;
int q[3000006];
int f[300006];
int gety(int x){
    return f[x];
}
int getx(int x){
    return sc[x];
}
int getk(int x){
    return s+st[x];
}
int find(int l,int r,int aim){
    int mid=0;
    int anss=ta;
    while(l<=r){
        mid=(l+r)>>1;
        if(gety(q[mid+1])-gety(q[mid])>aim*(getx(q[mid+1])-getx(q[mid]))){
            r=mid-1;
            anss=mid;
        }else{
            l=mid+1;
        }
    }
    return q[anss];
}
signed main(){
    read(n);read(s);
    for(int i=1;i<=n;++i){
        read(t[i]);read(c[i]);
        st[i]=st[i-1]+t[i];
        sc[i]=sc[i-1]+c[i];
    }
    q[++ta]=0;
    for(int i=1;i<=n;++i){
        int p=find(he,ta,getk(i));
        f[i]=f[p]+s*(sc[n]-sc[p])+st[i]*(sc[i]-sc[p]);
        //cout<<p<<endl;
        while(he<ta&&(gety(q[ta])-gety(q[ta-1]))*(getx(i)-getx(q[ta]))>=(gety(i)-gety(q[ta]))*(getx(q[ta])-getx(q[ta-1]))){ --ta;}
        q[++ta]=i;
        //cout<<f[i]<<endl;
    }
    printf("%lld",f[n]);
    return 0;
}