NOIP2023模拟2联测23 C. 负责

NOIP2023模拟2联测23 C. 负责

题目大意

给你 $n$ 个区间 $[l_i,r_i]$ ，每个区间有个 $w_i$ 。如果两个区间有交集（包括端点）那么两个区间就可以连边，形成一个图。

现在需要你删除一些区间，使得每个区间大小不超过 $k$ 。问最小删除的区间权值和。

思路

显然，想要断开一个连通块，那就是要把包含某个点的区间全部删掉。

设 $d{p}_i$ 表示只考虑在 $r_i$ 之前的区间，且 $r_i$ 是最后一个断开的地方的最大选的区间的权值和。

每次向后更新时加上区间的权值，如果区间个数大于 $k$ 就把权值最小的区间删掉，用一个堆维护。

时间复杂度 $O(n^{2}lo{g}_{2}n)$

code

#include 
#define fu(x , y , z) for(int x = y ; x <= z ; x ++)
#define LL long long
using namespace std;
const int N = 2505;
int n , k , b[N] , f[N];
LL sum , ans , dp[N];
struct Re {
    int l , r;
    LL w;
} re[N];
priority_queue<LL , vector<LL> , greater<LL>> q;
bool cmp (Re x , Re y) { return x.r != y.r ? x.r < y.r : x.l < y.l; }
int main () {
    scanf ("%d%d" , &n , &k);
    fu (i , 1 , n) {
        scanf ("%d%d%lld" , &re[i].l , &re[i].r , &re[i].w);
        sum += re[i].w;
    }
    sort (re + 1 , re + n + 1 , cmp);
    LL now;
    fu (i , 0 , n) {
        ans = max (ans , dp[i]);
        now = 0;
        while (!q.empty ())
            q.pop ();
        fu (j , i + 1 , n) {
            if (re[i].r < re[j].l) {
                now += re[j].w;
                q.push (re[j].w);
                if (q.size () > k) {
                    now -= q.top ();
                    q.pop ();
                }
            }
            dp[j] = max (dp[j] , ans + now);
        }
    }
    printf ("%lld" , sum - ans);
    return 0;
}
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