DDOSvoid's Blog

Luogu P2519 [HAOI2011]problem a

发表于 分类于
本文字数： 1.5k 阅读时长 ≈ 1 分钟

题目描述

https://www.luogu.com.cn/problem/P2519

给定 $n$ 个区间，选择若干不相交的区间使得选择的区间的价值和最大

Solution

有 $a_i$ 个人成绩高，有 $b_i$ 个人成绩低，实际上是告诉了我们有一段区间的人的分数相等

那么我们只需选择若干不相交的区间即可

一个小细节是相同区间不能超过区间长度个

时间复杂度 $O(n)$

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
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#define maxn 100010
#define cn const node
using namespace std;

int n;

struct node {
    int l, r, w;

    node(int _l = 0, int _r = 0) { l = _l; r = _r; }

    friend bool operator < (cn &u, cn &v) {
        if (u.l == v.l) return u.r < v.r; 
        return u.l < v.l;
    }

    friend bool operator == (cn &u, cn &v) { return u.l == v.l && u.r == v.r; } 
} a[maxn], b[maxn]; int c1, c2;

struct Edge {
    int to, next, w;
} e[maxn]; int c3, head[maxn];
inline void add_edge(int u, int v, int w) {
    e[c3].to = v; e[c3].w = w;
    e[c3].next = head[u]; head[u] = c3++;
} 

int f[maxn]; 
int main() { memset(head, -1, sizeof head); 
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        int x, y, l, r; scanf("%d%d", &x, &y);
        l = y + 1; r = n - x; if (l > r) continue;
        a[++c1] = node(l, r);
    }
    sort(a + 1, a + c1 + 1); 
    for (int i = 2, s = 1; i <= c1 + 1; ++i)
        if (a[i] == a[i - 1]) ++s;
        else {
            b[++c2] = a[i - 1];
            b[c2].w = min(s, a[i - 1].r - a[i - 1].l + 1);
            s = 1;
        }
    for (int i = 1; i <= c2; ++i) add_edge(b[i].r, b[i].l, b[i].w); 
    for (int u = 1; u <= n; ++u) {
        f[u] = f[u - 1]; 
        for (int i = head[u]; ~i; i = e[i].next) {
            int v = e[i].to, w = e[i].w;
            f[u] = max(f[u], f[v - 1] + w);
        }
    }
    cout << n - f[n] << endl; 
    return 0;
}