任务安排1,2:

$f_i=\min\{f_j+sumT_i*(sumC_i-sumC_j)+S*(sumC_n-sumC_j)\}$

费用提前计算 ,由于执行当前任务时,启动时间$S$会对$j+1\sim n$的任务产生影响,故加上。

就类似把竖着的,改成横着的,是等效的,如下图。

任务安排.png

任务安排(1).png

我们将转移式变形:

$f_i=\min\{f_j-(S+sumT_i)*sumC_j\}+sumT_i*sumC_i+S*sumC_n$

之后建关于$f_j$的直线,

$f_j=(S+sumT_i)*sumC_j-f_i-sumT_i*sumC_i-S*sumC_n$

之后斜率优化乱搞。

维护一个下凸壳,对于未来的$i$,注意是未来的,也就是斜率未确定的。

$(sumC_{j_2}-sumC_{j_1})*(S+sumT_i)>F_{j_2}-F_{j_1},(sumC_{j_3}-sumC_{j_2})*(S+sumT_i)<F_{j_3}-F_{j_2}$

$\frac{F_{j_2}-F_{j_1}}{sumC_{j_2}-sumC_{j_1}}<S*sumT_i<\frac{F_{j_3}-F_{j_2}}{sumC_{j_3}-sumC_{j_2}}$

即对于未来的$i$,$j_2$会成为最优解。

任务安排(2).PNG

至于为什么要维护一个下凸壳,由于斜率不断递增(也就是$i$在不断扩大),那么下凸壳的结构,也就正好满足了斜率不断递增的条件,会不断地通过弹出队头来更新答案。

单对着两个点来说,若$(sumC_{j_2}-sumC_{j_1})*(S+sumT_i)>F_{j_2}-F_{j_1}$,则说明$j_2$更优。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define gc getchar()
using namespace std;
const int N=5e3+5;
inline void qr(int &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(int x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int q[N],f[N],st[N],sc[N],S;
int main()
{
    int n;qr(n),qr(S);
    for(int i=1;i<=n;i++)qr(st[i]),qr(sc[i]),st[i]+=st[i-1],sc[i]+=sc[i-1];
    int l=1,r=1;q[1]=0;
    for(int i=1;i<=n;i++)
    {
        while(l<r&&(S+st[i])*(sc[q[l+1]]-sc[q[l]])>=f[q[l+1]]-f[q[l]])++l;
        f[i]=f[q[l]]+st[i]*(sc[i]-sc[q[l]])+S*(sc[n]-sc[q[l]]);
        while(l<r&&(f[i]-f[q[r]])*(sc[q[r]]-sc[q[r-1]])<=(f[q[r]]-f[q[r-1]])*(sc[i]-sc[q[r]]))--r;
        q[++r]=i;
    }
    qw(f[n]);puts("");
    return 0;
}

任务安排3

由于斜率不单调,可以考虑二分斜率,同时维护凸壳。

#include<cstdio>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<cstring>
#define gc getchar()
#define ll long long
using namespace std;
const int N=3e5+5;
template<class o>
inline void qr(o &x)
{
    x=0;char c=gc;int f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(ll x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int q[N],l,r;ll f[N],st[N],sc[N],S;
inline int get(int i)
{
    int k=S+st[i];
    if(l==r)return q[l];
    if(k*(sc[q[l+1]]-sc[q[l]])<f[q[l+1]]-f[q[l]])return q[l];
    if(k*(sc[q[r]]-sc[q[r-1]])>f[q[r]]-f[q[r-1]])return q[r];
    int L=l+1,R=r-1;
    while(L<R)
    {
        int mid=L+R>>1;
        if(k*(sc[q[mid+1]]-sc[q[mid]])>=f[q[mid+1]]-f[q[mid]])L=mid+1;
        else R=mid;
    }
    return q[L];
}
int main()
{
    int n;qr(n),qr(S);
    for(int i=1;i<=n;i++)qr(st[i]),qr(sc[i]),st[i]+=st[i-1],sc[i]+=sc[i-1];
    l=1,r=1;q[1]=0;
    for(int i=1;i<=n;i++)
    {
        int pos=get(i);
        f[i]=f[pos]+st[i]*(sc[i]-sc[pos])+S*(sc[n]-sc[pos]);
        while(l<r&&(f[i]-f[q[r]])*(sc[q[r]]-sc[q[r-1]])<=(f[q[r]]-f[q[r-1]])*(sc[i]-sc[q[r]]))--r;//无视斜率 
        q[++r]=i;
    }
    qw(f[n]);puts("");
    return 0;
}

任务安排4

横坐标和斜率都不单调,只好平衡树维护查询和插入了。

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdlib>
#define gc getchar()
#define ll long long
using namespace std;
const int N=3e5+10;
inline void qr(int &x)
{
    char c=gc;int f=1;x=0;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
    while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
    x*=f;
}
void qw(ll x)
{
    if(x<0)x=-x,putchar('-');
    if(x/10)qw(x/10);
    putchar(x%10+48);
}
int sc[N],st[N],S;ll dp[N];
struct node
{
    int id,son[2],f,prv,nxt;
}t[N];int len,root; 
inline bool compare(int i,int j,int k)
{
    return (dp[j]-dp[i])*(sc[k]-sc[j])>=(dp[k]-dp[j])*(sc[j]-sc[i]);
}
void rotate(int p,int w)
{
    int f=t[p].f,gf=t[f].f;
    int r=t[p].son[w],R=f;t[R].son[w^1]=r;if(r)t[r].f=R;
    r=p;R=gf;t[R].son[t[R].son[1]==f]=r;t[r].f=R;
    r=f;R=p;t[R].son[w]=r;t[r].f=R;
}
void splay(int p,int rt)
{
    while(t[p].f!=rt)
    {
        int f=t[p].f,gf=t[f].f;
        if(gf==rt)rotate(p,t[f].son[0]==p);
        else
        {
            if(t[f].son[0]==p&&t[gf].son[0]==f)rotate(f,1),rotate(p,1);
            else if(t[f].son[1]==p&&t[gf].son[0]==f)rotate(p,0),rotate(p,1);
            else if(t[f].son[0]==p&&t[gf].son[1]==f)rotate(p,1),rotate(p,0);
            else rotate(f,0),rotate(p,0);
        }
    }
    if(!rt)root=p;
}
void ins(int i)
{
    int p=root;
    if(!root){t[++len]=(node){i,{0,0},0,0,0};root=len;return ;}
    while(sc[t[p].id]!=sc[i])
    {
        if(sc[t[p].id]<sc[i])
        {
            if(!t[p].son[1])break;
            p=t[p].son[1];
        }
        else
        {
            if(!t[p].son[0])break;
            p=t[p].son[0];
        }
    }
    if(sc[t[p].id]<sc[i])
    {
        splay(p,0);
        if(!t[p].nxt)
        {
            t[++len]=(node){i,{0,0},p,p,0};
            t[p].son[1]=len;t[p].nxt=len;
            while(t[p].prv&&compare(t[t[p].prv].id,t[p].id,t[len].id))
            {
                t[t[p].prv].nxt=len;t[len].prv=t[p].prv;
                //t[p].prv=t[p].nxt=0;
                p=t[p].prv;
            }
            if(p)splay(p,0),splay(len,p),t[len].son[0]=0;
            else splay(len,0),t[len].son[0]=0;
        }
        else
        {
            int r=t[p].nxt;
            if(compare(t[p].id,i,t[r].id))return ;
            splay(r,p);
            t[++len]=(node){i,{0,0},r,p,r};
            int nxt=t[p].nxt;int prv=t[r].prv;
            t[p].nxt=len;t[r].prv=len;t[r].son[0]=len;
            while(t[nxt].nxt&&compare(i,t[nxt].id,t[t[nxt].nxt].id))
            {
                t[t[nxt].nxt].prv=len;t[len].nxt=t[nxt].nxt;
                //t[nxt].prv=t[nxt].nxt=0;
                nxt=t[nxt].nxt;
            }
            if(nxt)splay(len,0),splay(nxt,len),t[nxt].son[0]=0;
            else splay(len,0),t[len].son[1]=0;
            while(t[prv].prv&&compare(t[t[prv].prv].id,t[prv].id,i))
            {
                t[t[prv].prv].nxt=len;t[len].prv=t[prv].prv;
                //t[prv].nxt=t[prv].prv=0;
                prv=t[prv].prv;
            }
            if(prv)splay(prv,0),splay(len,prv),t[len].son[0]=0;
            else splay(len,0),t[len].son[0]=0;
        }
    }
    else
    {
        splay(p,0);
        if(!t[p].son[0])
        {
            t[++len]=(node){i,{0,0},p,0,p};
            t[p].son[0]=len;t[p].prv=len;
            while(t[p].nxt&&compare(t[len].id,t[p].id,t[t[p].nxt].id))
            {
                t[t[p].nxt].prv=len;t[len].nxt=t[p].nxt;
                //t[p].prv=t[p].nxt=0;
                p=t[p].nxt;
            }
            if(p)splay(len,0),splay(p,len),t[p].son[0]=0;
            else splay(len,0),t[len].son[1]=0;
        }
        else
        {
            int l=t[p].prv;
            if(compare(t[l].id,i,t[p].id))return ;
            splay(l,p);
            t[++len]=(node){i,{0,0},l,l,p};int nxt=t[l].nxt;int prv=t[p].prv;
            t[p].prv=len;t[l].nxt=len;t[l].son[1]=len;
            while(t[nxt].nxt&&compare(i,t[nxt].id,t[t[nxt].nxt].id))
            {
                t[t[nxt].nxt].prv=len;t[len].nxt=t[nxt].nxt;
                //t[nxt].prv=t[nxt].nxt=0;
                nxt=t[nxt].nxt;
            }
            if(nxt)splay(len,0),splay(nxt,len),t[nxt].son[0]=0;
            else splay(len,0),t[len].son[1]=0;
            while(t[prv].prv&&compare(t[t[prv].prv].id,t[prv].id,i))
            {
                t[t[prv].prv].nxt=len;t[len].prv=t[prv].prv;
                //t[prv].prv=t[prv].nxt=0;
                prv=t[prv].prv;
            }
            if(prv)splay(prv,0),splay(len,prv),t[len].son[0]=0;
            else splay(len,0),t[len].son[0]=0;
        }
    }
}
ll bz;
int solve(int p)
{
    int l=t[p].prv,r=t[p].nxt;
    bool pl=((dp[t[p].id]-dp[t[l].id])<=bz*(sc[t[p].id]-sc[t[l].id]));
    bool pr=((dp[t[r].id]-dp[t[p].id])<=bz*(sc[t[r].id]-sc[t[p].id]));
    if(!l&&!r)return t[p].id;
    else if(!l&&r)
    {
        if(pr)return solve(t[p].son[1]);
        return t[p].id;
    }
    else if(l&&!r)
    {
        if(pl)return t[p].id;
        return solve(t[p].son[0]);
    }
    else
    {
        if(pl==1&&pr==1)return solve(t[p].son[1]);
        if(pl==0&&pr==0)return solve(t[p].son[0]);
        return t[p].id;
    }
}/*
int solve(ll bz)
{
    int prv=t[p].prv,nxt=t[p].nxt;
    if(!prv&&!nxt)return t[p].id;6
    if(prv&&nxt)
    {
         
    }
}*/
int main()
{
    //freopen("a4.in","r",stdin);
    //freopen("a4.out","w",stdout);
    int n;qr(n);qr(S);
    for(int i=1;i<=n;i++)qr(st[i]),qr(sc[i]),st[i]+=st[i-1],sc[i]+=sc[i-1];
    st[0]=0,sc[0]=0;dp[0]=0;
    ins(0);
    for(int i=1;i<=n;i++)
    {
        bz=S+st[i];
        int p=solve(root);
        dp[i]=dp[p]+1ll*st[i]*(sc[i]-sc[p])+1ll*S*(sc[n]-sc[p]);
        //printf("%d\n",dp[i]);
        ins(i);
    }
    qw(dp[n]);puts("");
    return 0;
}