Painting the Fence 题解

题目传送门

一道枚举题。

我们可以直接枚举那 \(2\) 个去掉的粉刷匠。先统计一下每个栅栏会被多少个粉刷匠刷到，然后枚举第一个被去掉的粉刷匠，然后计算剩下的粉刷匠会将每个栅栏刷到多少次，我们只需要看只能被刷 \(1\) 次的栅栏就行了。

接着处理一个前缀和数组，记录前 \(i\) 个栅栏中有多少个只能被 \(1\) 个粉刷匠刷到。然后枚举第二个被去掉的粉刷匠，然后通过前缀和用 \(O(1)\) 的时间复杂度查询，别忘了加上前面第一个粉刷匠去掉后没有被刷的栅栏的数量。最后取最小值，与 \(n\) 相减即是答案。

Code

#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
using namespace std;
int n, q, minn = INF;
int l[5005], r[5005], cnt[5005], sum[5005];
signed main() {
    ios :: sync_with_stdio(0);
    cin >> n >> q;
    for (int i = 1; i <= q; i++) {
        cin >> l[i] >> r[i];
        for (int j = l[i]; j <= r[i]; j++) cnt[j]++;
    }
    for (int i = 1; i <= q; i++) {
        int x = 0;
        for (int j = l[i]; j <= r[i]; j++) cnt[j]--;
        for (int j = 1; j <= n; j++) {
            sum[j] = sum[j - 1];
            if (cnt[j] == 1) sum[j]++;
            if (cnt[j] == 0) x++;
        }
        for (int j = 1; j <= q; j++) {  
            if (j == i) continue;
            minn = min(minn, sum[r[j]] - sum[l[j] - 1] + x);
        }
        for (int j = l[i]; j <= r[i]; j++) cnt[j]++; // 别忘了要加回去继续枚举
    }
    cout << n - minn;
    return 0;
}