洛谷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;
}