洛谷P1868《饥饿的奶牛》

三月 09, 2019 2813

ProjectDP - 7

二分查找优化 DP

题目描述

有一条奶牛冲出了围栏，来到了一处圣地（对于奶牛来说），上面用牛语写着一段文字。

现用汉语翻译为：

有N个区间，每个区间x，y表示提供的x~y共y-x+1堆优质牧草。你可以选择任意区间但不能有重复的部分。

对于奶牛来说，自然是吃的越多越好，然而奶牛智商有限，现在请你帮助他。

输入输出格式

输入格式

第一行，N，如题

接下来N行，每行一个数x，y，如题

输出格式

一个数，最多能吃到的牧草堆数

输入输出样例

输入样例#1

3
1 3
7 8
3 4

输出样例#1

5

说明

1<=n<=150000

0<=x<=y<=3000000

解题思路

很容易想到设 dp[i] 表示前 i 个区间最多能选多少，转移从最优的 j\ (j<i) 中转移

时间复杂度 O(n^2) ，过不去

第一维 \forall i \in [1,n] 是雷打不动的，优化不了
考虑从第二维下手

首先 dp[] 数组是单调不降的很显然吧
那么只需要选择最近的一个「区间无交集」的 j 进行转移即可
这个 j 可以二分查找求得

如果找不到这个 j 的话就从上一次转移过来即可

转移方程：

dp[i] = \text{max}(dp[i-1],dp[j] \ \times\ (\text{j exists == true})
+ (\text{segment[i]'s left endpoint} - \text{segment[i]'s right endpoint} + 1))

中间那个 (\text{j exists == true}) 是个布尔表达式，它的返回值为0或1

至此，时间复杂度被降为 O(nlog_2n)

代码实现

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
//
//  7.cpp
//  ProjectDP
//
//  Created by HandwerSTD on 2019/3/9.
//  Copyright © 2019 Handwer STD. All rights reserved.
//

#include <algorithm>
#include <iostream>

#define FILE_IN(__fname) freopen(__fname, "r", stdin)
#define FILE_OUT(__fname) freopen(__fname, "w", stdout)
#define IMPROVE_IO() std::ios::sync_with_stdio(false)

using std::cin;
using std::cout;
using std::endl;

const int MAXN = 150000 + 10;

struct Segment {
    int l, r;
    
    Segment() { l = r = 0; }
    bool operator < (const Segment &that) const {
        if (r == that.r) return l < that.l;
        return r < that.r;
    }
} seg[MAXN];

int n, dp[MAXN];

int BinarySearch(int x) {
    int l = 1, r = x, ans = -2147482333;
    while (l <= r) {
        int mid = (l + r) >> 1;
        if (seg[mid].r < seg[x].l) {
            l = mid + 1;
            ans = mid;
        } else r = mid - 1;
    }
    return ans;
}

int main() {
    IMPROVE_IO();
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> seg[i].l >> seg[i].r;
    }
    std::sort(seg + 1, seg + 1 + n);
    for (int i = 1; i <= n; ++i) {
        int pre = BinarySearch(i);
        if (pre == -2147482333) dp[i] = std::max(dp[i - 1], seg[i].r - seg[i].l + 1);
        else dp[i] = std::max(dp[i - 1], dp[pre] + seg[i].r - seg[i].l + 1);
    }
    cout << dp[n] << endl;
    return 0;
}