[SDOI2005] 阶梯教室设备利用

发表于 | 分类于 >
字数统计 : 539   |   阅读时长 ≈ 3 mins.

题目

链接

[SDOI2005] 阶梯教室设备利用

题意简述

有 $n \ (n <= 10000)$ 个演讲，一次只能举行 $1$ 个。

某一演讲结束的瞬间可以立即开始另一个演讲。

计算最大的可能演讲总时间。

思路

DP

转移方程显而易见（设开始为 $l$ ，结束为 $r$ ）：

问题是不好转移啊2333。
考虑用线段树维护最大值。
单点更新，区间求最大值即可。
时间复杂度： $O(nlogn)$

代码

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
60
61
62
63
64
65
66
67
68
69
#include <bits/stdc++.h>
#define REG register
#define IN inline
#define For(x,y,z) for (REG int (x) = (y); (x) <= (z); ++(x))
#define FOR(x,y,z) for (REG int (x) = (y); (x) <  (z); ++(x))
const int kmax_num = 3e4 + 10, kmax_int = 2147483647, kmod = 1e9+7;

int n;
int f[kmax_num];

std::pair<int, int>	t[kmax_num];

struct SegmentTree {
    int val[kmax_num << 2];

    #define lson (root << 1)
    #define rson (root << 1) | 1

    inline void PushUp(REG int root) {
        val[root] = std::max(val[lson], val[rson]);
        return ;
    }

    inline void Update(REG int root, REG int begin, REG int end, REG int udp_begin, REG int udp_end, REG int num) {
        if(udp_begin <= begin && udp_end >= end) {
            val[root] = std::max(val[root], num);
            return;
        }
        else {
            REG int mid = (begin + end) >> 1;
            if(udp_begin <= mid)  Update(lson, begin, mid, udp_begin, udp_end, num);
            if(udp_end > mid)     Update(rson, mid + 1, end, udp_begin, udp_end, num);
            PushUp(root);
            return ;
        }
    }

    inline int Query(REG int root, REG int begin, REG int end, REG int que_begin, REG int que_end) {
        if(que_begin <= begin && que_end >= end) {
            return val[root];
        }
        else {
            REG int mid = (begin + end) >> 1, ans = -0x7fffffff;
            if(que_begin <= mid)  ans = std::max(ans, Query(lson, begin, mid, que_begin, que_end));
            if(que_end > mid)     ans = std::max(ans, Query(rson, mid + 1, end, que_begin, que_end));
            return ans;
        }
    }

    #undef lson
    #undef rson
} segment_tree;

int main() {
    std::cin >> n;

    REG int l, r;
    FOR(i,0,n)	std::cin >> l >> r, t[i].first = l, t[i].second = r;
    sort(t, t + n);

    FOR(i,0,n)	{
        l = t[i].first, r= t[i].second;
        f[r] = std::max(f[r], segment_tree.Query(1, 0, kmax_num - 1, 0, l) + r - l);
        segment_tree.Update(1, 0, kmax_num - 1, r, r, f[r]);
    }

    printf("%d\n", segment_tree.Query(1, 0, kmax_num - 1, 0, kmax_num - 1));
    return 0;
}

杂项

  • 这里记录开始和结束用了 $std::pair$ 实现，$std::pair$ 大法好！
  • 根本不需要 $std::pair$ 好不好！可以直接用两个数组实现！