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("%dn", res);
    return 0;
}