首页 > 其他 > 详细

【洛谷P1868】饥饿的奶牛

时间:2019-08-20 13:15:07      阅读:52      评论:0      收藏:0      [点我收藏+]

Description

给定若干个区间,每个区间的权值是该区间包含整数的个数,选出任意个不相交的区间使得权值和最大

Solution

dp+二分查找

定义状态$f[i]$表示前$i$个区间的最大值是多少

那么我们可以将区间排序后二分找到离当前区间最近的区间

我们的决策有两种:

如果能找到上述区间,那么我们可以用当前区间+最近的区间或者是前一个区间更新答案

如果找不到我们只能用上一个区间或者是当前区间更新答案

时间复杂度是$O(nlogn)$

Code

#include <bits/stdc++.h>
namespace shl {
    typedef long long ll;
    using std :: max;
    struct node {
        int x, y;
        bool operator <(const node &q) const {
            if (y != q.y) return y < q.y;
            return x < q.x;
        }
    } a[150010];
    int f[150010], n;
    inline int read() {
        int ret = 0, op = 1;
        char c = getchar();
        while (!isdigit(c)) {
            if (c == -) op = -1; 
            c = getchar();
        }
        while (isdigit(c)) {
            ret = (ret << 3) + (ret << 1) + c - 0;
            c = getchar();
        }
        return ret * op;
    }
    int query(int x) {
        int l = 1, r = x;
        int ans = -1;
        while (l <= r) {
            int mid = l + r >> 1;
            if (a[mid].y < a[x].x) {
                ans = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        return ans;
    }
    int main() {
        n = read();
        for (register int i = 1; i <= n; ++i) {
            a[i].x = read(), a[i].y = read();
        }
        std :: sort(a + 1, a + n + 1);
        f[1] = a[1].y - a[1].x + 1;
        for (register int i = 2; i <= n; ++i) {
            int ret = query(i);
            if (ret == -1) f[i] = max(f[i - 1], a[i].y - a[i].x + 1);
            else  f[i] = max(f[i - 1], f[ret] + a[i].y - a[i].x + 1);
        }
        printf("%d\n", f[n]);
        return 0;
    }
};
int main() {
    shl :: main();
    return 0;
}

 

【洛谷P1868】饥饿的奶牛

原文:https://www.cnblogs.com/shl-blog/p/11382158.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!