题解：P9691 [GDCPC 2023] Base Station Construction

单调队列优化 DP + 贪心

本题实际上就是给定若干条线段，要求在每个给出的线段中都至少要放一个点，求最后最小总代价是多少。

如果本题每个位置建立基站的权值都相同，则为经典贪心问题中的区间选点问题。

但本题每个位置建立基站的权值可以不同，于是不能直接按区间选点问题来处理，但是依然可以借助贪心思想。

考虑贪心：对于数轴中每个位置

i

，用

pre_i

记录这个位置前面距离位置

i

最近的上一个线段的左端点

j

，即使得

(j,i)

这段范围内不存在完整的线段，这样

[j,i]

这段区间就是就是必须要放的点的区间了，并且在这个区间内放一个点就尽可能多地覆盖给定的线段。

pre

数组的具体实现细节可见代码。

由于数轴中的位置值域不大，可以考虑 DP，并且由于存在多个上述的区间，需要考虑对于区间之间的转移，其实分析一下就会发现是一个单调队列优化 DP。

设

f_i

表示数轴

i

位置前面的必须放点的区间都已经放了且当前选择位置

i

放点所需的最小总代价。

DP 转移显然：

f_i = \min \{f_j\} + a_i \quad (pre_i \le j \le i-1)

最终答案即为 左端点最靠右的那条线段的左端点 到 右端点最靠右的那条线段的右端点 中产生，因为在这个范围内选点一定对应整个要求的区间的点都选完了。

即：

ans =\min \{ f_i \} \quad (pre_{n+1} \le i \le n)

时间复杂度

\mathcal O(n)

。

代码如下：

CPP

#define rep(x,y,z) for(int x=y;x<=z;x++)
typedef long long LL;
const int N=5e5+5;
int n,m;
int a[N];
int q[N];
LL f[N];
int pre[N];
void solve(){
	cin>>n;
	rep(i,1,n) cin>>a[i];
	rep(i,1,n+1) pre[i]=f[i]=0;
	cin>>m;
	while(m--){
		int l,r;
		cin>>l>>r;
		pre[r+1]=max(pre[r+1],l);
	}
	rep(i,1,n+1) pre[i]=max(pre[i],pre[i-1]);
	int hh=1,tt=0;
	rep(i,1,n){
		while(hh<=tt && f[q[tt]]>=f[i-1]) tt--;
		q[++tt]=i-1;
		while(q[hh]<pre[i]) hh++;
		f[i]=f[q[hh]]+a[i];
	}
	LL ans;
	memset(&ans,0x3f,sizeof ans);
	rep(i,pre[n+1],n) ans=min(ans,f[i]);
	cout<<ans;
}

题解：P9691 [GDCPC 2023] Base Station Construction

文章操作

单调队列优化 DP + 贪心

相关推荐

评论

题解：P9691 [GDCPC 2023] Base Station Construction