UPD:
修复了代码中一个数组越界的问题，并进行卡常，使得不开O2也能轻松过题
这题在学校听了老板讲，然而并没有听懂个啥（
然后自己重新定状态，推式子，优化（
IEE
吐槽翻译。题面
Solution
首先将每个救生牛的工作时段抽象为线段。则题意变为，给你 $N$ 条线段，要你删除 $K$ 条，使得剩下的线段覆盖最多的点。为了方便描述，令 $l_i=s_i$，$r_i=t_i$
很多题解一上来先去掉了什么”不需要保留的线段”。其实我认为正常做题应该是想好了如何动规再根据动规需求删除这些没有保留价值的线段。
朴素做法的状态与方程
根据数据范围，设 $f[i][j]$ 表示前 $i$ 条线段，删除了 $j$ 条，剩下的线段最多可以覆盖多少个点。
方程为：$f[i][j]=max${$f[k][j-i+k+1]+r_i-max(l_i,r_k)$}$(i-j-1\le k\le i-1,i\le N,j\le K)$
然而时间复杂度 $O(NK^2)$，如果对自己的常数与厌氧程度不够自信建议放弃
优化DP
上述内容自己稍加思考便能想到。难的是优化。
状态数肯定逃不了，想办法在 $O(K)$ 的转移上做手脚。
根据动规优化的套路，将式子中与 $k$ 无关的项硬提出来。令 $x=j-i+1$。
则原式变为：$f[i][j]=max\{f[k][x+k]+r_i-max(l_i,r_k)\}$
现在很讨厌的是里面的那个 $max$。我们尝试用干掉绝对值的方法干掉这个 $max$—分类讨论。
如果 $r_k\le l_i$，相当于要 $f[k][x+k]$ 最大。
如果 $r_k>l_i$，相当于要 $f[k][x+k]-r_k$ 最大。
为了方便维护，我们考虑将每条线段按左端点排序。这样方便确定计算顺序。
现在，如果按传统的for(i 1......n),for(j 1......k)计算很不方便。
考虑按照 $x=j-i+1$ 划分阶段。$1$ 是常数，相当于按照 $j-i$ 划分阶段。
我们发现，所有能转移到状态 $f[i][j]$ 的状态 $f[x][y]$ 必定满足 $y-x=j-i+1$。所以，状态 $f[i][j]$ 能转移到的状态 $f[x_1][y_1]$ 满足 $y_1-x_1=j-i-1$。
因此按照 $j-i$ 倒序计算每个状态。将所有 $j-i=0$ 的状态设为 $0$（相当于所有线段全部删除）。
这样，就相当于在所有范围内的 $k$ 中，对于 $r_k\le l_i$ 的情况（情况1）取一个最大值，对于 $r_k>l_i$ （情况2）取一个最大值。
考虑使用前缀和sum维护情况1，单调队列维护情况2。因为所有线段按照左端点排好了序，所以在 $x=j-i-1$ 确定的情况下，从小到大枚举 $j$（个人认为枚举 $j$ 方便，枚举 $i$ 当然也没有任何问题），$i$ 也是从小到大的，$r_{i-1}$ 也是从小到大的。（为什么是 $i-1$，因为 $i-j-1\le k\le i-1$），$l_{i-1}$ 也是从小到大的。
等等！线段只按照左端点进行了排序，为什么 $r_{i-1}$ 也”天然有序”？仔细想想，如果有两条线段 $i$，$j$，$l_i\le l_j$ 且 $r_i\ge r_j$，线段 $j$ 无论保留还是删除都不会影响结果。换句话说，$j$ 被 $i$ 完全覆盖了，我们应该在预处理时删掉这种线段。如果预处理完已经删除了超过 $K$ 条线段直接将所有线段覆盖的点数输出即可。
扯了半天，回到式子。单调队列装下每个方案对应的 $k$，每次检查单调队列首部的元素 $k$ 是否 $r_k\le l_i$，如果是，将这个方案的 $f[k][x+k]$ 计算出来，与 $sum$ 比较取大值。单调队列pop_front()。然后根据各个线段的情况决定 $k=i-1$ 放到单调队列里还是直接更新前缀和。
时间复杂度：$O(NK)$。因为单调队列每个元素最多只会有一次进队和出队的机会。
细节见代码。
$Code:$
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
| #include <stdio.h>
#include <algorithm>
#include <string.h>
inline int min(const int x, const int y) {return x < y ? x : y;}
inline int max(const int x, const int y) {return x > y ? x : y;}
const int MaxN = 100001, INF = 0x3fffffff;
struct Line {
int l, r;
inline bool operator < (const Line x) const {return l < x.l;}
} a[MaxN];
template<int MAXSIZE> struct deque {
int head, tail, a[MAXSIZE];
deque() {head = 0, tail = -1;}
inline void clear() {head = 0, tail = -1;}
inline void push_back(int x) {a[++ tail] = x;}
inline void pop_back() {-- tail;}
inline void pop_front() {++ head;}
inline int size() {return tail - head + 1;}
inline int front() {return a[head];}
inline int back() {return a[tail];}
};
deque<1005> q;
int f[MaxN][101], L[MaxN], R[MaxN], n;
int main() {
int N, K, ans(-INF), MaxR(-INF);
scanf("%d%d", &N, &K);
memset(f, ~0x3f, sizeof f);
for (int i(1); i <= N; ++ i) scanf("%d%d", &a[i].l, &a[i].r);
std::sort(a + 1, a + N + 1);
for (int i(1); i <= N; ++ i) if (a[i].r > MaxR)
L[++ n] = a[i].l, R[n] = a[i].r, MaxR = a[i].r;
K -= N - n;
if (K <= 0) {
int ans(0), MaxR(L[1]);
for (int i(1); i <= n; ++ i) ans += R[i] - max(MaxR, L[i]), MaxR = R[i];
printf("%d", ans);
return 0;
}
for (int i(0); i <= K; ++ i) f[i][i] = 0;
for (int k(-1); k >= -n; -- k) {
int x(k + 1), sum(-INF);
q.clear();
for (int j(0); j <= min(K, n + k); ++ j) {
int i(j - k);
while (q.size() && R[q.front()] <= L[i])
sum = max(sum, f[q.front()][x + q.front()]), q.pop_front();
if (R[i - 1] <= L[i]) sum = max(sum, f[i - 1][x + i - 1]);
else {
while (q.size() && f[q.back()][x + q.back()] - R[q.back()] <=
f[i - 1][x + i - 1] - R[i - 1]) q.pop_back();
q.push_back(i - 1);
}
f[i][j] = sum - L[i] + R[i];
if (q.size()) f[i][j] = max(f[i][j], f[q.front()][x + q.front()] - R[q.front()] + R[i]);
}
}
for (int i(n - K); i <= n; ++ i) ans = max(ans, f[i][K - n + i]);
printf("%d", ans);
return 0;
}
|