CF-1132C Painting the Fence 题解

题目大意

有p个人，每个人负责一个区域，让你从中选p-2个人，求覆盖的最大面积。

解题思路

因为数据不大，刚开始就想着是用直接暴力。

但是纯粹的暴力的话，复杂度是$O(n^3)$。

估计铁超时。

后面就想着用差分吧，但是每次都需要一个前缀和。

也觉得会超时，后面想了好久，没想到什么好的方法。

卡了我好久，没办法了，看题解去了。

发现与我的思路就差了一个前缀和。

通过这个前缀和，把$O(n^3)$优化到$O(n^2)$了。

真的没想到用前缀和来维护区间中这次去掉人之后所会减少的面积。

太难想了。。。

整体思路就是先统计每一个位置上被覆盖了多少次，然后反向思维，枚举掉需要去掉的两个人。

在枚举第一个人的时候，需要修改统计的数组，最后需要记得还原，同时dp出前缀和数组，这个数组表示从1~i中有多少是覆盖次数为1的，也就是这次会去掉的个数。

完整代码

#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;
}