专栏文章

题解：P10981 任务安排 4.2

__Acheron_
P10981题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqp47wl
此快照首次捕获于
2025/12/04 08:26
3 个月前
此快照最后确认于
2025/12/04 08:26
3 个月前
查看原文

前言

一文弄懂基础斜率优化。
因为 P2365 是纯 dp，和斜率优化无关，暂且不表。
各代码敲的时间相隔有点久，马蜂不太一样。

前置知识

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

P10979

我们先把 P2365 的转移式搬过来：
fi=min⁡j=0i−1{fj+sumTi×(sumCi−sumCj)+s×(sumCn−sumCj)}f_i=\min_{j=0}^{i-1}\{f_j+sumT_i\times(sumC_i-sumC_j)+s\times(sumC_n-sumC_j)\}
其中带 sumsum 前缀表示前缀和。
我们来愉快地化一下式子：
fi=fj+sumTisumCi−sumTisumCj+s×sumCn−s×sumCj=fj−(sumTi+s)sumCj+sumTisumCi+s×sumCn\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}
我们把只和 jj 有关的项放到左边，其余放到右边，可得：
fj=(sumTi+s)sumCj+sumTisumCi+s×sumCn+fif_j=(sumT_i+s)sumC_j+sumT_isumC_i+s\times sumC_n+f_i
事实上，我们把不和 ii 有关的项放到左边或者右边都行。但是我们仍以上式为例。
令 y=fj,k=sumTi+s,x=sumCj,b=sumTisumCi+s×sumCn+fiy=f_j,k=sumT_i+s,x=sumC_j,b=sumT_isumC_i+s\times sumC_n+fi，那么我们可得式子：
y=kx+by=kx+b
这是小学二年级就学过的一次函数的形式。
具体的，我们对于每个点 jj，看成在平面直角坐标系的一点 (x,y)(x,y)，那么当 ii 从 jj 转移时，fif_i 的值会被更新为经过点 (x,y)(x,y) 的斜率为 kk 的直线的截距的值减去 sumTisumCi+s×sumCnsumT_isumC_i+s\times sumC_n。当 ii 确定时，后面跟的一坨式子就是个定值，不用管它，所以我们相当于要求一个点 jj，使得经过点 (x,y)(x,y) 的斜率为 kk 的直线的截距最小。
类似于这样：
思考一下，什么时候截距能够取到最小值？
如下，现在有一条斜率固定为 kk 的直线。一开始，它在很低的地方（即截距很小），我们把它慢慢上移（即截距慢慢变大）：
触及的第一个点即为最优决策点。
类似这样。
那么，什么样的点会第一个被碰到呢？
一个点会第一个被碰到，说明这个点在这坨点的“外部”，不会被一些点“包含在内”。如果你学过对应的知识，可以知道会被碰到的点在所有点的凸包上。
再进一步，因为直线是从下往上移动的，所以这些点需要再“外部的下面”，即在下凸壳上。
类似这样：
瞪眼观察，即可发现下凸壳上相邻线段斜率单调递增。
也就是说，我们要维护一坨点，满足相邻线段斜率递增，这些点才有可能成为最优转移点。
那么对于不同的斜率，那个才是最优转移点呢？
观察一下以下这种情况：
瞪眼观察不难发现，假设直线为 kk 的直线和凸壳的切点为 ii，则 i−1i-1 到 ii 之间线段的斜率小于 kk，ii 到 i+1i+1 之间线段的斜率大于 kk。
既然如此，我们的大体思路就是加点进凸壳中，并找到一个位置，满足其之前的线段的斜率都小于 kk。
我们重回原题。
注意到这道题有很好的性质，即 sumTi≥sumTi−1,sumCi≥sumCi−1sumT_i\ge sumT_{i-1},sumC_i\ge sumC_{i-1}。这说明 xx 和 kk 单调。
对于 xx 单调，这方便了我们插入一个点进入凸壳。显然，xx 坐标最大的点一定在凸壳上，因此，我们可以用一个栈维护凸壳中的点，栈顶为 xx 最大的点，当目前栈顶的点不满足凸壳的限制（斜率递增），就弹掉栈顶元素，然后就能把这个点加入凸壳了。
对于 kk 单调，方便我们找决策点。因为 kk 单调，所以决策点也单调。我们也可以用一个栈维护凸壳中的点，栈顶为 xx 最小的点。当栈顶不是最优决策点时，直接弹栈，直到找到最优决策点即可。
也就是说，我们综合起来需要一个“能弹栈顶和栈底的栈”，也就是双端队列。因为队列里的元素是单调的，所以也是单调队列。
好的，这道题你已经做完了。

code

CPP
#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

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

code

CPP
#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

终于讲到正题了！
当 xx 和 kk 都不单调时，一般有如下做法：
1. 平衡树
考虑使用平衡树动态维护凸壳。当插入一个点时，先判断其是否在凸包内部，如果不是，则弹掉其左右两边不合法的点，再插入。当查询决策点时，查找后继即可。
优点是非常暴力，简单易懂。缺点是常数大，难写，基本被后面的做法完爆。
2. 李超线段树
我们重化一下那个式子：
fi=fj+sumTisumCi−sumTisumCj+s×sumCn−s×sumCjfi−sumTisumCi−s×sumCn=−sumCjsumTi+fj−s×sumCj\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=−sumCj,b=fj−s×sumCjk=-sumC_j,b=f_j-s\times sumC_j，则可以看做每次插入一条直线 y=kx+by=kx+b，每次求 x=sumTix=sumT_i 时所有直线上的最大值。套李超线段树模板即可。因为 sumTisumT_i 的值域较大，需要离散化。
优点是实现简洁，缺点是做法难以扩展。
3. CDQ 分治
暂时不会，可以去其它题解看看。

code

写的是李超。因为暂时没有数据，所以不保证代码一定正确。
CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...