题解：P10981 任务安排 4.2

_Acheron_ · 2024-12-22 20:44:58 · 题解

前言

一文弄懂基础斜率优化。

因为 P2365 是纯 dp，和斜率优化无关，暂且不表。

各代码敲的时间相隔有点久，马蜂不太一样。

前置知识

P2365 简单版做法，平衡树/李超线段树/CDQ 分治。

P10979

我们先把 P2365 的转移式搬过来：

f_i=\min_{j=0}^{i-1}\{f_j+sumT_i\times(sumC_i-sumC_j)+s\times(sumC_n-sumC_j)\}

其中带 sum 前缀表示前缀和。

我们来愉快地化一下式子：

\begin{aligned} f_i&=f_j+sumT_isumC_i-sumT_isumC_j+s\times sumC_n-s\times sumC_j\\ &=f_j-(sumT_i+s)sumC_j+sumT_isumC_i+s\times sumC_n\\ \end{aligned}

我们把只和 j 有关的项放到左边，其余放到右边，可得：

f_j=(sumT_i+s)sumC_j+sumT_isumC_i+s\times sumC_n+f_i

事实上，我们把不和 i 有关的项放到左边或者右边都行。但是我们仍以上式为例。

令 y=f_j,k=sumT_i+s,x=sumC_j,b=sumT_isumC_i+s\times sumC_n+fi，那么我们可得式子：

y=kx+b

这是小学二年级就学过的一次函数的形式。

具体的，我们对于每个点 j，看成在平面直角坐标系的一点 (x,y)，那么当 i 从 j 转移时，f_i 的值会被更新为经过点 (x,y) 的斜率为 k 的直线的截距的值减去 sumT_isumC_i+s\times sumC_n。当 i 确定时，后面跟的一坨式子就是个定值，不用管它，所以我们相当于要求一个点 j，使得经过点 (x,y) 的斜率为 k 的直线的截距最小。

类似于这样：

思考一下，什么时候截距能够取到最小值？

如下，现在有一条斜率固定为 k 的直线。一开始，它在很低的地方（即截距很小），我们把它慢慢上移（即截距慢慢变大）：

触及的第一个点即为最优决策点。

类似这样。

那么，什么样的点会第一个被碰到呢？

一个点会第一个被碰到，说明这个点在这坨点的“外部”，不会被一些点“包含在内”。如果你学过对应的知识，可以知道会被碰到的点在所有点的凸包上。

再进一步，因为直线是从下往上移动的，所以这些点需要再“外部的下面”，即在下凸壳上。

类似这样：

瞪眼观察，即可发现下凸壳上相邻线段斜率单调递增。

也就是说，我们要维护一坨点，满足相邻线段斜率递增，这些点才有可能成为最优转移点。

那么对于不同的斜率，那个才是最优转移点呢？

观察一下以下这种情况：

瞪眼观察不难发现，假设直线为 k 的直线和凸壳的切点为 i，则 i-1 到 i 之间线段的斜率小于 k，i 到 i+1 之间线段的斜率大于 k。

既然如此，我们的大体思路就是加点进凸壳中，并找到一个位置，满足其之前的线段的斜率都小于 k。

我们重回原题。

注意到这道题有很好的性质，即 sumT_i\ge sumT_{i-1},sumC_i\ge sumC_{i-1}。这说明 x 和 k 单调。

对于 x 单调，这方便了我们插入一个点进入凸壳。显然，x 坐标最大的点一定在凸壳上，因此，我们可以用一个栈维护凸壳中的点，栈顶为 x 最大的点，当目前栈顶的点不满足凸壳的限制（斜率递增），就弹掉栈顶元素，然后就能把这个点加入凸壳了。

对于 k 单调，方便我们找决策点。因为 k 单调，所以决策点也单调。我们也可以用一个栈维护凸壳中的点，栈顶为 x 最小的点。当栈顶不是最优决策点时，直接弹栈，直到找到最优决策点即可。

也就是说，我们综合起来需要一个“能弹栈顶和栈底的栈”，也就是双端队列。因为队列里的元素是单调的，所以也是单调队列。

好的，这道题你已经做完了。

code

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=3e5+5;
int n,s,head=1,tail,t[N],c[N],q[N],f[N];
int Y(int i){
    return f[i];
}
int X(int i){
    return c[i];
}
int K(int i){
    return t[i]+s;
}
signed main(){
    scanf("%lld%lld",&n,&s);
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&t[i],&c[i]);
        t[i]+=t[i-1];
        c[i]+=c[i-1];
    }
    q[++tail]=0;
    for(int i=1;i<=n;i++){
        while(head<tail&&Y(q[head+1])-Y(q[head])<=K(i)*(X(q[head+1])-X(q[head]))) head++;
        f[i]=f[q[head]]+t[i]*(c[i]-c[q[head]])+s*(c[n]-c[q[head]]);
        while(head<tail&&(Y(q[tail])-Y(q[tail-1]))*(X(i)-X(q[tail]))>=(Y(i)-Y(q[tail]))*(X(q[tail])-X(q[tail-1]))) tail--;
        q[++tail]=i;
    }
    printf("%lld",f[n]);
    return 0;
}

P5785

在这题中，T_i 可以为负数，则 sumT_i 不单调，也就是 k 不单调。因此，我们在找决策点时就不能单纯的弹队列取队头了。因为下凸壳的斜率单调，我们可以二分出第一个点 i 满足 i 到 i+1 的线段的斜率大于 k，取改点为决策点即可。事实上，这样做后，单调队列退化成了单调栈。

code

#include<bits/stdc++.h>
#define int __int128
using namespace std;
namespace fastIO{
    #define f_inline inline __attribute__((always_inline))
    char buf[3145728],*p1 = buf,*p2 = buf;
    f_inline char gc(){return (p1 == p2 && (p2 = (p1 = buf) + fread(buf,1,3145728,stdin),p1 == p2) ? EOF : *p1++);}
    template <typename T>f_inline T read(){//读入一个数字
        register T x = 0,f = 1;char ch = gc();
        while(!isdigit(ch)){if(ch == '-')f = -1;ch = gc();}
        while(isdigit(ch)){x = (x << 1) + (x << 3) + (ch ^ 48),ch = gc();}
        return f * x;
    }
    char buffer[1048576];int _p1 = -1;const int _p2 = 1048575;
    f_inline void flush(){fwrite(buffer,1,_p1 + 1,stdout),_p1 = -1;}
    f_inline void putchar(const register char &x){if(_p1 == _p2)flush();buffer[++_p1] = x;}
    template <typename T>inline void write(T x){//输出一个数字
        if(x < 0){putchar('-'),x = -x;}
        const register T tmp = x / 10;
        if(x > 9)write(tmp);
        putchar(x - (tmp << 1) - (tmp << 3) ^ 48);
    }
};
using namespace fastIO;
const int N=3e5+5;
int n,s,p,head=1,tail,t[N],c[N],f[N],q[N];
int find(int l,int r,int x){
    int mid;
    while(l<=r){
        mid=l+r>>1;
        if(f[q[mid+1]]-f[q[mid]]>=x*(c[q[mid+1]]-c[q[mid]])) r=mid-1;
        else l=mid+1;
    }
    return l;
}
signed main(){
    n=read<int>();
    s=read<int>(); 
    for(int i=1;i<=n;i++){
        t[i]=read<int>();
        c[i]=read<int>();
        t[i]+=t[i-1];
        c[i]+=c[i-1];
    }
    memset(f,0x7f,sizeof(f));
    f[0]=0;
    q[++tail]=0;
    for(int i=1;i<=n;i++){
        p=find(head,tail-1,t[i]+s);
        f[i]=f[q[p]]-(t[i]+s)*c[q[p]]+t[i]*c[i]+s*c[n];
        while(head<tail&&(f[q[tail]]-f[q[tail-1]])*(c[i]-c[q[tail-1]])>=(f[i]-f[q[tail-1]])*(c[q[tail]]-c[q[tail-1]])) tail--;
        q[++tail]=i;
    }
    write<int>(f[n]);
    flush();
    return 0;
}

P10980

除了三小只（平衡树/李超线段树/CDQ 分治）以外没想到什么更加简便的做法，有的话欢迎私聊。

P10981

终于讲到正题了！

当 x 和 k 都不单调时，一般有如下做法：

1. 平衡树

考虑使用平衡树动态维护凸壳。当插入一个点时，先判断其是否在凸包内部，如果不是，则弹掉其左右两边不合法的点，再插入。当查询决策点时，查找后继即可。

优点是非常暴力，简单易懂。缺点是常数大，难写，基本被后面的做法完爆。

2. 李超线段树

我们重化一下那个式子：

\begin{aligned} f_i&=f_j+sumT_isumC_i-sumT_isumC_j+s\times sumC_n-s\times sumC_j\\ f_i-sumT_isumC_i-s\times sumC_n&=-sumC_jsumT_i+f_j-s\times sumC_j \end{aligned}

令 k=-sumC_j,b=f_j-s\times sumC_j，则可以看做每次插入一条直线 y=kx+b，每次求 x=sumT_i 时所有直线上的最大值。套李超线段树模板即可。因为 sumT_i 的值域较大，需要离散化。

优点是实现简洁，缺点是做法难以扩展。

3. CDQ 分治

暂时不会，可以去其它题解看看。

code

写的是李超。因为暂时没有数据，所以不保证代码一定正确。

#include<bits/stdc++.h>
#define int long long
#define ls (k<<1)
#define rs (k<<1|1)
using namespace std;
const int N=3e5+5;
int n,s,idx,cnt,T[N],C[N],f[N],liser[N];
struct seg{
    int k,b;
}p[N];
struct node{
    int l,r,num;
}t[N<<2];
int calc(seg p,int x){
    return p.k*x+p.b;
}
void add(int k,int b){
    p[++idx]={k,b};
}
void build(int k,int l,int r){
    t[k].l=l;
    t[k].r=r;
    if(l==r) return;
    int mid=l+r>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
}
void modify(int k,int x){
    int mid=t[k].l+t[k].r>>1;
    if(calc(p[x],liser[mid])<calc(p[t[k].num],liser[mid])) swap(t[k].num,x);
    if(calc(p[x],liser[t[k].l])<calc(p[t[k].num],liser[t[k].l])) modify(ls,x);
    if(calc(p[x],liser[t[k].r])<calc(p[t[k].num],liser[t[k].r])) modify(rs,x);
}
int query(int k,int x){
    if(x<t[k].l||t[k].r<x) return 1e18;
    if(t[k].l==t[k].r) return calc(p[t[k].num],liser[x]);
    return min(min(query(ls,x),query(rs,x)),calc(p[t[k].num],liser[x]));
}
signed main(){
    scanf("%lld%lld",&n,&s);
    p[0].b=1e18;
    for(int i=1;i<=n;i++){
        scanf("%lld%lld",&T[i],&C[i]);
        T[i]+=T[i-1];
        C[i]+=C[i-1];
        liser[++cnt]=T[i];
    }
    sort(liser+1,liser+cnt+1);
    cnt=unique(liser+1,liser+cnt+1)-liser-1;
    for(int i=1;i<=n;i++) T[i]=lower_bound(liser+1,liser+cnt+1,T[i])-liser;
    build(1,1,cnt);
    add(0,0);
    modify(1,idx);
    for(int i=1;i<=n;i++){
        f[i]=query(1,T[i])+liser[T[i]]*C[i]+s*C[n];
        add(-C[i],f[i]-s*C[i]);
        modify(1,idx);
    }
    printf("%lld",f[n]);
    return 0;
}