题解 P1868 【饥饿的奶牛】
zhy137036
2020-02-28 20:20:45
这篇题解记录了我做这道题的思考过程。
## 题意简述
- 给你 $n$ 个区间 $(x,y)$，长度为 $y-x+1$。
- 选择不相交的几个区间，使长度之和最大。
- 两个区间 $(x_1,y_1)$ 和 $(x_2,y_2)$ 不相交，当且仅当 $y_1<x_2$ 或 $y_2<x_1$。
- $1\le x\le1.5\times10^5$，$0\le x\le y\le3\times10^6$。
## 题目分析
有人曾经说过：你不会的题很可能就是动态规划。
这道题就是动态规划。
区间？感觉是线性动态规划，再看数据范围，没错了。
### 状态定义
首先不妨想象这些草地是一个一个的格子。
先从最简单的定义想起：
设 $f_i$ 表示前 $i$ 个格子最多能吃到多少牧草。
虽然这个定义很简单，但是很好用。
### 转移式
显然 $f_j\ge f_{j-1}$。多一个格子选择，吃得总不会更少。
如果有一个区间 $(i,j)$，那么 $f_j\ge f_{i-1}+j-i+1$。
最后得到转移式：
$$\large f_j=\max(f_{j-1},\max f_{i-1}+j-(i-1))$$
### 细节处理
但是怎么对于所有的 $j$ 都知道对应的所有的 $i$ 呢？
发现一个 $j$ 所对应的 $i$ 的个数是不固定的，所以想到用 `std::vector<int>` 保存。
## 代码
自认为代码比较简洁。
```cpp
#include<cstdio>
#include<algorithm>
#include<vector>
using namespace std;
vector<int>beg[3000010];//有点大，不过并不会 MLE
int n,mx,f[3000010];//mx 代表最大的 y，f 就是 dp 用的数组
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x,y;
scanf("%d%d",&x,&y);
beg[y].push_back(x-1);//这里保存的是 x-1，后面会比较方便
mx=max(mx,y);
}
for(int i=1;i<=mx;i++){
f[i]=f[i-1];//先设定为 f[i-1]，后面再更新
for(int j=0;j<beg[i].size();j++){
int b=beg[i][j];
f[i]=max(f[i],f[b]+i-b);//这里会比较方便
}
}
printf("%d\n",f[mx]);
return 0;
}
```