洛谷P1868 饥饿的奶牛 题解

题目链接：P1868 饥饿的奶牛

题意：

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

现用汉语翻译为：

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

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

$1 \leq n \leq 1.5 \times 10^5$，$0 \leq x \leq y \leq 3 \times 10^6$。

设 $f_i$ 表示只考虑前 $i$ 个位置能吃到的最多牧草

$$f_i = \max_{j \in \text{Edge}(i)}\left\{f_{j-1} + i-j+1\right\}$$

这里的 $\text{Edge}(i)$ 表示以 $i$ 结尾的所有区间组成的集合

对于每个区间 $[x,y]$ ，我们建一条 $y \to x$ 的边

这样就可以枚举 $j$ 了

时间复杂度 $O(m)$

代码：

#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iomanip>
#include <random>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(1.5e5+15)
#define M (int)(3e6+15)
struct Edge{int u,v,next;}e[N];
int n,l,pos=1,f[M],head[M];
void addEdge(int u,int v)
{
    e[++pos]={u,v,head[u]};
    head[u]=pos;
}
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n;
    for(int i=1,u,v; i<=n; i++)
    {
        cin >> u >> v;
        addEdge(v,u);
        l=max(l,v);
    }
    for(int u=1; u<=l; u++)
    {
        f[u]=f[u-1];
        for(int i=head[u]; i; i=e[i].next)
        {
            int v=e[i].v;
            f[u]=max(f[u],f[(!v)?0:v-1]+(u-v+1));
        }
    }
    cout << f[l] << '\n';
    return 0;
}