有p个人，每个人负责一个区域，让你从中选p-2个人，求覆盖的最大面积。
解题思路
因为数据不大，刚开始就想着是用直接暴力。
但是纯粹的暴力的话，复杂度是。
估计铁超时。
后面就想着用差分吧，但是每次都需要一个前缀和。
也觉得会超时，后面想了好久，没想到什么好的方法。
卡了我好久，没办法了，看题解去了。
发现与我的思路就差了一个前缀和。
通过这个前缀和，把O(n^3)优化到O(n^2)了。
真的没想到用前缀和来维护区间中这次去掉人之后所会减少的面积。
太难想了。。。
整体思路就是先统计每一个位置上被覆盖了多少次，然后反向思维，枚举掉需要去掉的两个人。
在枚举第一个人的时候，需要修改统计的数组，最后需要记得还原，同时dp出前缀和数组，这个数组表示从1~i中有多少是覆盖次数为1的，也就是这次会去掉的个数。
完整代码
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
| #include <iostream>
#include <algorithm>
using namespace std;
int l[5050], r[5050], cnt[5050], flag[5050], fs[5050];
int main() {
int n, q; cin >> n >> q;
int sum = 0;
for (int i = 1; i <= q; i++) {
cin >> l[i] >> r[i];
for (int j = l[i]; j <= r[i]; j++) {
cnt[j]++;
if (cnt[j] && !flag[j]) flag[j] = 1, sum++;
}
}
int ans = 0;
for (int i = 1; i <= q; i++) {
int s = 0;
for (int j = l[i]; j <= r[i]; j++) {
cnt[j]--;
if (!cnt[j]) s++;
}
for (int j = 1; j <= n; j++) {
if (cnt[j]==1) fs[j] = fs[j - 1] + 1;
else fs[j] = fs[j - 1];
}
int m = 1e9;
for (int j = i+1; j <= q; j++) {
m = min(m, fs[r[j]] - fs[l[j] - 1]);
}
for (int j = l[i]; j <= r[i]; j++) cnt[j]++;
ans = max(ans, sum - s - m);
}
cout << ans << endl;
}
|
