自动搬运

查看原文

来自洛谷，原作者为

	Unordered_OIer **

搬运于2025-08-24 21:57:25，当前版本为作者最后更新于2020-09-06 16:12:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

P4182 题解

题意

提供 $n$ 个区间，要求删去 $k$ 个区间后剩下的区间覆盖长度最大。

（吐槽本题翻译，看英文才看懂的）

建模

我们先从一些特殊情况考虑。如果区间 $A$ 完全覆盖区间 $B$ ，那么删去这样的 $B$ 区间完全没有用，因此我们先删除这种情况。

接下来，不难看出我们可以先对所有的区间进行一次排序，并且可以证明按照左端点排序或者右端点排序后，左端点和右端点都保持升序。

证明如下：
如果存在左端点 $l_i \leq l_{i+1}$ 且 $r_i \geq r_{i+1}$ ，那么区间 $i$ 完全覆盖区间 $i+1$ ，这种情况在一开始的特殊情况考虑中就已经被删除。
$∴$ 不存在 $l_i \leq l_{i+1}$ 且 $r_i \geq r_i+1$ ，因此一定左右端点都保持升序，证毕。

然后我们就可以进行区间 $dp$ 了。

根据题目，我们设 $f[i][j]$ 表示前 $i$ 个区间，删除 $j$ 个的最大覆盖长度。但是转移的时候，存在的问题是并不确定覆盖的状态，不方便转移。

具体化 $f[i][j][S]$ 表示前 $i$ 个区间，删除 $j$ 个，状态为 $S$ 的最大覆盖长度？爆空间。

因此我们最好把状态控制在 $2$ 维，且要具体化，因此我们可以这样定义： $f[i][j]$ 表示前 $i$ 个区间，删除 $j$ 个的最大覆盖长度，$\color{red}{\normalsize{\mathbf{并且限制选第}}}$ $\color{red}{i}$ $\color{red}{\normalsize{\mathbf{个}}}$。

转移方程：

$$f[i][j]=\max\{f[k][j-\text{len}(k,i)],R[i]-\max(L[i],R[k])\}\ |\ k<i $$

其中 $\text{len}(l,r)=r-l-1$

复杂度 $\Theta(n \times k^2)$ ，明显 $\colorbox{#052242}{\text{\color{white}TLE}}$ 。

优化

我们继续把转移方程贴一遍：

$$f[i][j]=\max\{f[k][j-\text{len}(k,i)],R[i]-\max(L[i],R[k])\}\ |\ k<i $$

把它转化一下：

$$f[i][j]=\max\{f[k][k-\text{len}(k,i)],R[i]-L[i]\}\ |\ \text{\footnotesize{对于比较小的}}\ k $$

如果我们能够用预计算把 $\Theta(k)$ 的转移变为 $\Theta(1)$ 的，那么总复杂度即为 $\Theta(nk)$ ，对于这种情况就 $\colorbox{#52C41A}{\text{\color{white}{AC}}}$ 了。

这是对于较小的 $k$ 的情况。

那么对于较大的 $k$ 的情况？
这时的转移方程是：

$$f[i][j]=\max\{f[k][k-\text{len}(k,i)],R[i]-R[k]\}$$

记 $que\_t$ 表示所有 $f[k][k+t]-R[k]$ 的最大值，单调队列即可。

那如果 $k$ 有限制，不能太小？还是单调队列。

当 $k$ 有限制，第二种情况在哪里求最大值？
$f[i][j]=que\_t[j-i+1]$ 队列里的首位 $+R[i]$ （不满足 $L[i]<R[k]$ 就离队，顺便更新 $que\_t[j-i+1]$ ）。
并且，我们同时将 $f[i][j]$ 用 $que\_t[j-i+1]$ 来更新一下。

算完之后，更新单调队列，把 $f[i][j]-R[i]$ 插入到 $que\_t[j-i]$ 的单调队列里，即可。

那么我们理一下思路：

1. 计算 $f[i][j]$ 时，把 $que\_t[i-j-1]$ 中队首表示的区间不与 $i$ 相交的踢出去。
2. 当前队首是最大值。
3. 计算 $f[i][j]$ 并更新 $que\_t[i-j]$ 。

复杂度 $\Theta(nk)$ ，可以 $\colorbox{#52C41A}{\text{\color{white}{AC}}}$ 。

代码还是放一下吧，细节比较多，注意不要复制。

//lifeguards P 防Copy版
for(ll i=1;i<=n*k;i++){
	ll u=min(k+1,i);
	for(ll j=0;j<n;j++){
		ll now_pos=i-j-1;
		while(!increasing_queue[now_pos].empty()&&sequence[increasing_queue[now_pos].front().node].r<sequence[i].l){
			Node tt_next=increasing_queue[now_pos].front();
			rr[now_pos]=max(rr[now_pos],tt_next.val+sequence[tt_next.node].r);
			increasing_queue[now_pos].pop_front();
		}
		f[i][j]=max(f[i][j],rr[now_pos]+sequence[i].r-sequence[i].l);
		if(!increasing_queue[now_pos].empty())f[i][j]=max(f[i][j],increasing_queue[now_pos].front().val+sequence[i].r);
		ll now_val=f[i][j]-sequence[i].r;
		now_pos=i-j;
		while((!increasing_queue[now_pos].empty())&&(increasing_queue[now_pos].back().val<now_val))increasing_queue[now_pos].pop_back();
		increasing_queue[now_pos].push_back((Node){i,now_val});
	}
}//在一定程度上参考了其他人的代码（我不会告诉你是因为我写的太丑了）
for(int i=1;i<=n;i++)ans=max(ans,f[i][k]);

完结撒花~

看在我码了这么多字，给个赞吧。