NOIP2023模拟2联测23 C. 负责

• NOIP2023模拟2联测23 C. 负责
  • 题目大意
  • 思路
  • code

题目大意

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

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

思路

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

设 \(dp_i\) 表示只考虑在 \(r_i\) 之前的区间，且 \(r_i\) 是最后一个断开的地方的最大选的区间的权值和。

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

时间复杂度 \(O(n^2log_2n)\)

code

#include <bits/stdc++.h>
#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;
}