P1868 饥饿的奶牛

P1868 饥饿的奶牛

题意:

有 \(N\) 个区间，每个区间 \(x,y\) 表示提供的 $s \sim y $ 共 \(y - x + 1\) 堆牧草，可以选择任意区间，但是选的区间不能有重复部分。求最多可以获得多少堆牧草

思路:

肯定先根据 \(x\) 来进行排序，定义 \(f[i]\) 为到达第 \(i\) 个点可以获得的最多牧草。

当我们到达一个 \(x\) 的时候，这段到第 \(y\) 段中间肯定都不能有其他东西，所以 \(f[y] = y - x + 1\) ，然后如果之前有区间在 \(x\) 之前就结束的话，也可以加上，所以我们用 \(last\) 来记录 \(f[1] \sim f[x - 1]\) 时的最大值，然后对当前点可以加上即 \(f[y] += last\)

实现:

#include <bits/stdc++.h>
using namespace std;
const int N = 3e6 + 5;
int f[N];
pair<int, int> a[N];
int main()
{
    int n;
    scanf("%d", &n);
    for (int i = 1; i <= n; i++)
        scanf("%d%d", &a[i].first, &a[i].second);
    sort(a + 1, a + 1 + n);
    int res = 0, j = 0, last = 0;
    for (int i = 0; i < N; i++)
    {
        while (j + 1 <= n && a[j + 1].first == i)
        {
            j++;
            f[a[j].second] = max(f[a[j].second], last + (a[j].second - a[j].first + 1));
        }
        res = max(res, f[i]);
        last = max(last, f[i]);
    }
    printf("%d\n", res);
    return 0;
}