LG-P4182 [USACO18JAN]Lifeguards P Solution

更好的阅读体验戳此进入

解法本身题解区已经写的较为清楚了，这里主要对大多数题解都涉及到但均未证明的一个贪心策略进行感性证明，故前面的推导过程写的较为简略。

题面

给定 $n$$n$ 个左闭右开的区间，在范围 $[0,{10}^9]$$[0, 10^{9}]$ 内，最大化删去其中 $k$$k$ 个区间后剩下区间并起来的长度，求最大值。

$1\le n\le {10}^5,1\le k\le min(100,n)$$1 \le n \le 10^5, 1 \le k \le \min(100, n)$。

Solution

首先不难想到对于区间 $[l_1,r_1),[l_2,r_2)$$[l_1, r_1), [l_2, r_2)$ 且 $l_1\le l_2\wedge r_2\le r_1$$l_1 \le l_2 \land r_2 \le r_1$ 那么删去 $[l_2,r_2]$$[l_2, r_2]$ 答案一定不变，于是可以直接全部删去，并将 $k\leftarrow k-1$$k \leftarrow k - 1$。

然后 DP 显然，也很好想到一个状态 $dp(i,k)$$dp(i, k)$ 表示考虑前 $i$$i$ 个区间，删去其中的 $k$$k$ 个的最优值，然后发现这玩意没有固定具体怎么删没法转移，然后就想到在原来的状态基础上钦定必须选择第 $i$$i$ 个区间，然后需要把区间优先按左端点，再按右端点排序，这样我们就会发现最开始去掉那些区间的作用了，去掉之后现在我们剩下的区间排序后一定满足对于 $l$$l$ 的升序一定也满足 $r$$r$ 升序，不满足的已经被我们删掉了。于是此时转移比较显然：$dp(i,k)=max\{dp(j,k-(i-j-1))+r_i-max(l_i,r_j)\},j\in [i-k-1,i-1]$$dp(i, k) = \max\{ dp(j, k - (i - j - 1)) + r_i - \max(l_i, r_j) \}, j \in [i - k - 1, i - 1]$。这玩意复杂度显然是 $O(n{k}^2)$$O(nk^2)$ 的，显然不正确。

考虑优化，状态没什么可优化的，于是考虑优化转移，我们尝试提出来与转移时的 $j$$j$ 无关的项，令 $\xi =i-k-1$$\xi = i - k - 1$，于是有 $dp(i,k)=max\{dp(j,j-\xi )+r_i-max(l_i,r_j)\},j\in [i-k-1,i-1]$$dp(i, k) = \max\{ dp(j, j - \xi) + r_i - \max(l_i, r_j) \}, j \in [i - k - 1, i - 1]$。也就是说我们要在 $\xi =i-k-1$$\xi = i - k - 1$ 的前提下，换句话说就是以前的 $dp$$dp$ 中前后索引的差为 $\xi$$\xi$ 的值中找到后面式子的最大值进行转移，这个东西简单分类讨论一下就是如果 $l_i\ge r_j$$l_i \ge r_j$（或者理解为区间无交）那么就是要最大化 $dp(j,j-\xi )$$dp(j, j - \xi)$。反之需要最大化 $dp(j,j-\xi )-r_j$$dp(j, j - \xi) - r_j$。

所以我们直接对前者维护一个最大值（因为我们的区间之间使有序的，所以如果对于之前的区间已经无交了，对于现在的一定也无交），后者则维护一个单调队列单调栈单调双端队列，每次处理时先把对应单调双端队列队头中所有不合法的，也就是不交的弹出然后更新不交区间里面的最大值。然后用交的和不交的里的最大值更新当前 $dp$$dp$，每次处理完当前的 $dp$$dp$ 就把当前的丢到对应的单调双端队列里，这时我们会按照双端队列直接把队尾不优于当前的直接丢掉而不是保留下来等待不交时更新不交的最大值，这个的原因我想了很久，感性地证明了一下，如下：

如果你仔细想一下就会发现这个算法有一点问题，首先我们在最初的找单调双端队列里面的队头不合法的值的时候，我们时按照 $val$$val$ 的大小，也就是 $dp(j,j-\xi )-r_j$$dp(j, j - \xi) - r_j$ 的大小维护的单调双端队列，但是我们更新不交最大值的时候需要的是与其不交区间里的最大值（废话），难道就不会存在一种情况，即队头的区间 $val$$val$ 更大，但是区间靠右，然而队头之后某个区间 $val$$val$ 较小却区间靠左，也就是存在一种情况单调优先队列的后面已经存在了不交的区间但是却被队头的相交区间阻挡了，这样的话我们难道不会少更新一些值吗？还有就是在把当前的 $dp$$dp$ 压入单调双端队列的时候，我们会把队尾不优于当前值的直接踢掉，这个时候却没有考虑到在后面更新时这些区间可能会从相交变成不交，从而可能性地去更新不交的最大值，但是现在这被我们丢掉了，难道不会使答案更劣吗？

这几个问题困扰了我很久，完全没有头绪，直到发现了一个性质我才大概能感性理解这个贪心的正确性。

显然当我们转移的时候，如果转移的这个 $j$$j$ 是与 $i$$i$ 交的，那么最优的 $j$$j$ 一定是 $l_j$$l_j$ 最小的 $j$$j$，当然经过我们的处理之后同时也是 $r_j$$r_j$ 最小的。这个不难理解，因为我们处理过包含的区间，所以 $i,j$$i, j$ 相交那么最终这两段组成的区间一定是 $[l_j,r_i)$$[l_j, r_i)$，那么 $l_j$$l_j$ 尽量小一定更优，所以 $j+1,j+2,\cdots ,i-1$$j + 1, j + 2, \cdots, i - 1$ 的区间都是没必要选的，选了也不会有任何贡献。

此时我们再回到刚才的考虑，我们的单调优先队列维护的是最大值，而最大值一定是 $l$$l$ 和 $r$$r$ 最小的，那么我们实际上也可以感性地认为更左的区间在单调双端队列里也更靠前，如果这个成立那么我们刚才的所有问题也就很显然是不需要考虑得了，这样的话我们弹出的队头一定是最先变得不交的，被丢掉的区间也一定是更劣的。

于是这个贪心（应该）是正确的。

当然上面这一大段证明都完全是我口糊的，不保证正确性，也不够理性和严谨，期待一个更严谨的证明。

Code

xxxxxxxxxx
86
1
#define _USE_MATH_DEFINES
2
#include <bits/extc++.h>
3

4
#define PI M_PI
5
#define E M_E
6
#define npt nullptr
7
#define SON i->to
8
#define OPNEW void* operator new(size_t)
9
#define ROPNEW(arr) void* Edge::operator new(size_t){static Edge* P = arr; return P++;}
10

11
using namespace std;
12
using namespace __gnu_pbds;
13

14
mt19937 rnd(random_device{}());
15
int rndd(int l, int r){return rnd() % (r - l + 1) + l;}
16
bool rnddd(int x){return rndd(1, 100) <= x;}
17

18
typedef unsigned int uint;
19
typedef unsigned long long unll;
20
typedef long long ll;
21
typedef long double ld;
22

23
template< typename T = int >
24
inline T read(void);
25

26
struct Line{
27
    int l, r;
28
    friend const bool operator < (const Line &a, const Line &b){if(a.l == b.l)return a.r < b.r; return a.l < b.l;}
29
}line[110000];
30
list < Line > _line;
31
int N, K;
32
int cnt(0);
33
struct Status{int idx; int val;};
34
deque < Status > bst[110000];
35
int mx[110000];
36
int dp[110000][110];
37

38
int main(){
39
    N = read(), K = read();
40
    for(int i = 1; i <= N; ++i){
41
        int l = read(), r = read();
42
        _line.emplace_back(Line{l, r});
43
    }_line.sort();
44
    for(auto it = next(_line.begin()); it != _line.end();)
45
        if(it->r <= prev(it)->r)it = _line.erase(it), --K; else ++it;
46
    for(auto ln : _line)line[++cnt] = ln;
47
    N = cnt; K = max(0, K);
48
    for(int i = 1; i <= N; ++i){
49
        for(int k = 0; k <= min(i - 1, K); ++k){
50
            int xi = i - k - 1;
51
            while(!bst[xi].empty() && line[bst[xi].front().idx].r < line[i].l){
52
                auto tp = bst[xi].front(); bst[xi].pop_front();
53
                mx[xi] = max(mx[xi], tp.val + line[tp.idx].r);
54
            }
55
            dp[i][k] = max({
56
                dp[i][k],
57
                mx[xi] + line[i].r - line[i].l,
58
                bst[xi].empty() ? -1 : bst[xi].front().val + line[i].r
59
            });
60
            int val = dp[i][k] - line[i].r;
61
            int pos = i - k;
62
            while(!bst[pos].empty() && bst[pos].back().val < val)bst[pos].pop_back();
63
            bst[pos].push_back(Status{i, val});
64
        }
65
    }int ans(-1);
66
    for(int i = N - K; i <= N; ++i)ans = max(ans, dp[i][K - (N - i)]);
67
    printf("%d\n", ans);
68
    fprintf(stderr, "Time: %.6lf\n", (double)clock() / CLOCKS_PER_SEC);
69
    return 0;
70
}
71

72
template < typename T >
73
inline T read(void){
74
    T ret(0);
75
    short flag(1);
76
    char c = getchar();
77
    while(c != '-' && !isdigit(c))c = getchar();
78
    if(c == '-')flag = -1, c = getchar();
79
    while(isdigit(c)){
80
        ret *= 10;
81
        ret += int(c - '0');
82
        c = getchar();
83
    }
84
    ret *= flag;
85
    return ret;
86
}

UPD

update-2022_11_03 初稿