题目大意
题面
歪歪要追 T 集电视剧。对每一集，电视剧长度为 L 分钟，她预先给出 n 个可能想看的片段，第 i 个片段是闭区间 [l_i, r_i]。
她会从这些片段里选出若干个两两不重叠的片段。注意这里是闭区间，所以 [1, 3] 和 [3, 5] 算重叠，[1, 3] 和 [4, 5] 才不重叠。
同时，男明星会在这一集的 m 个时刻出现，分别是 a_i。歪歪要求每个被选择的片段里，都至少能看到一次男明星。
问在这个前提下，一集最多能看多少分钟。
输入格式
第一行输入 T。
每组数据先输入 L, n, m。
接下来 n 行输入 l_i, r_i。
最后一行输入 m 个 a_i。
数据范围
-
T <= 10
-
L <= 1e9
-
n, m <= 1e5
-
1 <= a_i <= L
-
1 <= l_i <= r_i <= L
样例
1
2
3
4
5
6
7
8
9
10
11
| 2
10 5 3
1 2
3 3
1 6
4 10
8 10
1 3 10
10 1 5
6 10
1 2 3 4 5
|
输出：
思路讲解
一句话
先用二分筛掉“不含明星出现时刻”的片段，剩下的问题就是经典的带权区间选择：每个合法区间的权重是长度，按右端点排序后做 DP。
第一步：判断一个片段能不能看
把所有明星出现时刻 a_i 排序。对片段 [l, r]，用 lower_bound(a, l) 找到第一个 >= l 的出现时刻。
如果这个位置存在，并且值 <= r，说明片段里至少出现了一次男明星，这个片段可以进入后面的 DP。
这个筛选是 O(log m) 的，所以 n 个片段总共 O(n log m)。
第二步：把问题看成带权区间选择
筛完以后，每个片段都有一个权重：
w=r−l+1
现在要从这些区间里选若干个互不重叠的区间，让权重和最大。
闭区间的边界非常关键：前一个区间的右端点必须严格小于当前区间左端点，也就是 r_prev < l_now。
按右端点从小到大排序。设 dp[i] 表示只考虑前 i 个合法区间时，最多能看的分钟数。
对当前区间 [l_i, r_i]，有两种选择：
于是转移就是：
dp[i]=max(dp[i−1],dp[j]+wi)
这里 j 可以用 lower_bound(right, l_i) - 1 找到。
第三步：为什么要考虑“单独选当前区间”
这题最容易挂的地方不是大方向，而是这个小分支。
如果当前区间前面没有任何能接上的前驱，也就是 lower_bound(right, l_i) 指向开头，它仍然可以单独选。
所以当前区间的贡献至少应该参与一次比较：
1
| dp[i] = max(dp[i - 1], lr[i].w);
|
然后如果存在前驱，再尝试：
1
| dp[i] = max(dp[i], dp[j] + lr[i].w);
|
反例很小：
两个区间都合法，但互相重叠。最优应该单独选 [2, 100]，答案是 99。若没有“单独选当前区间”这个分支，就会错误地保留 [1, 5]，输出 5。
复杂度
排序明星出现时刻、排序区间，再对每个片段二分一次。
总复杂度 O((n + m) log n)，空间 O(n + m)。
AC 代码
AC 提交链接
源码较长，折叠放在下面。
展开完整源码
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
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
|
#include <bits/stdc++.h>
#define all(vec) vec.begin(), vec.end()
#define lson(o) (o << 1)
#define rson(o) (o << 1 | 1)
#define SZ(a) ((long long)a.size())
#define fsp(x) fixed << setprecision(x)
using namespace std;
#if 1 && defined(LOCAL)
namespace DBG {
template<typename T> void debug(T x);
void debug(bool x);
void debug(string x);
template<typename T> void debug(vector<T> v);
template<typename T, size_t N> void debug(array<T, N> v);
template<typename T> void debug(set<T> s);
template<typename T, typename U> void debug(pair<T, U> p);
template<typename T, typename U> void debug(map<T, U> m);
template<typename, typename = void> constexpr bool _has_iter_v = false;
template<typename T> constexpr bool _has_iter_v<T, void_t<decltype(declval<T>().begin()), decltype(declval<T>().end())>> = true;
template<typename T>
void debug(T x) { cerr << x; } void debug(bool x) { cerr << (x ? "T" : "F"); } void debug(string x) { cerr << '"' << x << '"'; }
template<typename T> void debug(vector<T> v) { constexpr bool nested = _has_iter_v<T>; int n = v.size(); cerr << "["; for (int i = 0; i < n; i++) { if constexpr (nested) { if (i) cerr << ","; cerr << "\n "; } else { if (i) cerr << ", "; } debug(v[i]); } if constexpr (nested) { if (n) cerr << "\n"; } cerr << "]"; }
template<typename T, size_t N> void debug(array<T, N> v) { constexpr bool nested = _has_iter_v<T>; cerr << "["; for (size_t i = 0; i < N; i++) { if constexpr (nested) { if (i) cerr << ","; cerr << "\n "; } else { if (i) cerr << ", "; } debug(v[i]); } if constexpr (nested) { if (N) cerr << "\n"; } cerr << "]"; }
template<typename T> void debug(set<T> s) { cerr << "{"; int f = 0; for (auto x: s) { if (f++) cerr << ", "; debug(x); } cerr << "}"; }
template<typename T, typename U> void debug(pair<T, U> p) { cerr << "("; debug(p.first); cerr << ", "; debug(p.second); cerr << ")"; }
template<typename T, typename U> void debug(map<T, U> m) { cerr << "{"; int f = 0; for (auto &[k, v]: m) { if (f++) cerr << ", "; debug(k); cerr << ": "; debug(v); } cerr << "}"; }
void _dbg() { cerr << endl; }
template<typename T, typename... A> void _dbg(T x, A... a) { debug(x); if (sizeof...(a)) cerr << ", "; _dbg(a...); }
}
#define dbg(x...) cerr << "[" << setw(7) << #x << "] = ", DBG::_dbg(x)
#define cend cerr << "\n---------------------------------------------------\n"
#define cEnd cerr << "\n***************************************************\n"
#define myAssert(...) assert((__VA_ARGS__))
#else
#define dbg(x...) 11
#define cend 45
#define cEnd 14
#define myAssert(x) 14
#endif
using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;
static constexpr ll MAXN = (ll)1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353;
static constexpr double eps = 1e-8;
const long double PI = acosl(-1.0);
ll lT, testcase;
struct LR {
ll l, r, w;
bool operator<(const LR& o) const {
if (r != o.r) return r < o.r;
return l < o.l;
}
};
void Solve() {
ll L, N, M;
cin >> L >> N >> M;
vector<LR> lr;
lr.reserve(N);
for (int i = 0; i < N; ++i) {
ll l, r;
cin >> l >> r;
lr.push_back({l, r, 0});
}
sort(all(lr));
vector<ll> A(M);
for (int i = 0; i < M; ++i) {
cin >> A[i];
}
sort(all(A));
vector<ll> right;
do {
vector<LR> lrBack;
lrBack.reserve(N);
for (int i = 0; i < N; ++i) {
auto it = lower_bound(all(A), lr[i].l);
if (it == A.end()) continue;
if (*it <= lr[i].r) {
lr[i].w = lr[i].r - lr[i].l + 1;
lrBack.push_back(lr[i]);
right.push_back(lr[i].r);
}
}
swap(lrBack, lr);
} while (false);
vector<ll> dp(SZ(lr));
if (dp.empty()) {
cout << "0\n";
return;
}
dp[0] = lr[0].w;
for (int i = 1; i < SZ(lr); ++i) {
auto it = lower_bound(all(right), lr[i].l);
dp[i] = max(dp[i - 1], lr[i].w);
if (it == right.begin()) {
continue;
}
it--;
int j = it - right.begin();
dp[i] = max(dp[i], dp[j] + lr[i].w);
}
dbg(dp);
cout << dp.back() << "\n";
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
#ifdef LOCAL
cout.setf(ios::unitbuf);
#endif
cin >> lT;
for (testcase = 1; testcase <= lT; ++testcase)
Solve();
return 0;
}
|
心路历程（WA，TLE，MLE……）
-
一开始 DP 大方向是对的：合法片段筛选 + 按右端点排序 + 找前驱。
-
坑点出在当前区间没有前驱的时候，代码直接 continue，漏掉了“当前区间单独作为答案”的情况。
-
修法是先执行 dp[i] = max(dp[i - 1], lr[i].w)，再在存在前驱时尝试拼上前驱。
-
这类带权区间 DP 可以记一句话：当前区间要么不选，要么自己开一段，要么接在一个合法前驱后面。
附件
暂无额外附件。