P1868题解 - 洛谷保存站

## P1868题意概述

从 $n$ 个 $[l_i,r_i]$ 的区间中任取若干个互不相交区间，  
使得这些区间的长度之和最大。

## 初步思路分析
很显然：这是一道动态规划的题目。  
双倍经验： [P2439](https://www.luogu.com.cn/problem/P2439)。

### 状态定义及其转移
定义 $f_i$ 为前 $i$ 个格子最多能吃到的牧草。  
显然 $f$ 序列单调不减 即 $f_i \ge f_{i-1}$ 。  
（毕竟多一个格子选择又不会变少）

不难发现，  
当存在以 $i$ 为右端点的区间 $[l,i]$ 时，  
转移公式如下:
$$
f_i= \max(f_j,f_{l-1}+i-l+1) \text{ , 其中 } j<i
$$
但是问题又来了，
如果我们直接枚举 $r_i$ 转移，若此时 $f_{l_i-1}$ 还未更新怎么办呢?
### 进一步细化思路
有dalao使用300000个vector存左端点，  
直接值域从小到大挨个枚举。

但蒟蒻提供一种新思路：  
首先以右端点升序对区间进行排序。
```cpp
struct node{
	int x,y;
	bool operator <(const node &b)const{
		if(y==b.y) return x<b.x;
		else return y<b.y;
	}
}q[N];
```
不难发现每次真正有效可被用于赋予最大值的转移，  
只发生在区间 $[l,r]$ 中从 $l_i$ 到 $r_i$ 的转移。

于是，在枚举每个区间时，  
将从上个区间右端点 $r_{i-1}$ 到这个区间右端点 $r_i$ 的所有 $f_j$ 关于 $f_{r_{i-1}}$ 取最大值。
```cpp
for(int j=ly+1;j<=ny;j++) f[j]=max(f[ly],f[j]);
```
这样便可以确保计算 $f_{r_i}$ 时 $f_{l_i-1}$ 必定取最大值。

##  代码实现 
```cpp
#include<bits/stdc++.h>
using namespace std;
#define N 150005
#define M 3000006
int read(){
	int x=0;char ch=getchar();
	while(ch<'0'||ch>'9') ch=getchar();
	while(ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
	return x;
}
struct node{
	int x,y;
	bool operator <(const node &b)const{
		if(y==b.y) return x<b.x;
		else return y<b.y;
	}
}q[N];
int n,f[M];
int main(){
	n=read();
	for(int i=1;i<=n;i++) q[i].x=read()-1,q[i].y=read();
//注意本人此处用的左开右闭
	sort(q+1,q+n+1);
	for(int i=1;i<=n;i++){
		int ly=q[i-1].y,nx=q[i].x,ny=q[i].y;
		for(int j=ly+1;j<=ny;j++) f[j]=max(f[ly],f[j]);
		f[ny]=max(f[ny],f[nx]+(ny-nx));
	}
	printf("%d",f[q[n].y]);
	return 0;
} 
```
有兴趣的下去可以试试离散化。（~~虽然我也不确定行不行~~）

正在渲染内容...