题解 P4182 【[USACO18JAN]Lifeguards P】
Unordered_OIer
·
·
题解
P4182 题解
题意
提供 n 个区间，要求删去 k 个区间后剩下的区间覆盖长度最大。
（吐槽本题翻译，看英文才看懂的）
建模
我们先从一些特殊情况考虑。如果区间 A 完全覆盖区间 B ，那么删去这样的 B 区间完全没有用，因此我们先删除这种情况。
接下来，不难看出我们可以先对所有的区间进行一次排序，并且可以证明按照左端点排序或者右端点排序后，左端点和右端点都保持升序。
证明如下：
如果存在左端点 l_i \leq l_{i+1} 且 r_i \geq r_{i+1} ，那么区间 i 完全覆盖区间 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]$ 来更新一下。
算完之后，更新单调队列，把 $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}}}$ 。
代码还是放一下吧，细节比较多，注意不要复制。
```cpp
//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]);
```
完结撒花~
看在我码了这么多字，给个赞吧。