更好的阅读体验

题目描述

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

现用汉语翻译为：

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

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

输入格式

第一行，$N$，如题

接下来$N$行，每行一个数$x$，$y$

输出格式

一个数，最多能吃到的牧草堆数

输入输出样例

输入 #1

3
1 3
7 8
3 4

输出 #1

3
1 3
7 8
3 4

数据范围

$$ 1 \le n \le 1.5 \times 10^5 \\\\0 \le x \le y \le 3 \times 10^6 $$

解题报告

题意理解

就是给你一些区间,要求选择的区间包含以下条件.

1. 选取区间总长度最大
2. 选取的区间之间不得用重叠部分,包括区间左右端点部分

算法解析

首先这道题目的数据范围,比较具有特色,让人不难想到和线性复杂度的算法挂上钩.

然后因为具有,明显的最值性质,我们不难设置这道题目的算法为,线性DP

我们接着考虑,如何进行,动态规划的流程

状态设计

解决一道动态规划的题目,最主要的就是状态设计和状态转移

一个个区间,都包含了$[l,r]$,因此我们可以设置.

每一个点,作为分段点

因此,我们得出了.
$$ f[i]表示[1,i]区间的最大利润 $$

状态转移

假如说,我们现在位于$i$这个节点处.

那么对于这个点而言,显然包含它的区间的右端点一定为$i$

换种表达为
$$ [s,i]为包含这个端点的区间 $$
当然$s$是属于一类集合,也就是,所有右端点为$i$的区间.

因此我们不难推导出转移方程.
$$ f[i]=f[i-1] \quad 不选择当前任何一个区间 \\\\f[i]=max(f[i],f[s_j]+(i-s_j+1)) \quad 选择[s_j,i]这个区间 \\\\i-s_j+1为该区间的利润 $$

算法解析

#include <bits/stdc++.h>
using namespace std;
const int M=3000000+10;
vector<int> g[M];
int f[M],n,m,ans,r;
inline void init()
{
    scanf("%d",&n);
    for(int i=1; i<=n; i++)
    {
        int a,b;
        scanf("%d%d",&a,&b);
        r=max(r,b);//找到最大右区间
        g[b].push_back(a);//记录区间[a,b]
    }
    for(int i=1; i<=r; i++)//当前区间[1,i]
    {
        f[i]=f[i-1];//如果本次不选择任何区间,就是这样
        for(int s:g[i])//找到以当前点作为终点的区间
            f[i]=max(f[i],f[s-1]+(i-s+1));//s表示这个区间的左端点,那么就是表示选择这个区间s
        //[s,i]表示本次区间,那么他可以带来的代价为(s-i+1),
    }
    printf("%d\n",f[r]);
}
signed main()
{
    init();
    return 0;
}