自动搬运

查看原文

来自洛谷，原作者为

	mzgwty **

搬运于2025-08-24 21:31:15，当前版本为作者最后更新于2019-04-09 13:14:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

表示蒟蒻完全没有想出来线性怎么做

膜一下写出O(n)算法的dalao

方程很简单

f[i]表示前i个区间能选到的最大数量

f[i]=max(f[i-1],f[j]+a[i].tail-a[i].head+1);//j表示尾小于当前区间头且f最大的区间下标

这个DP其实是个n^2算法，肯定过不了。

于是看有找尾小于当前头的一重O(n)的循环，就考虑利用二分查找优化一下，所以就要先按尾从小到大排序，然后再来dp

inline int lower_bound(int l,int r,int key) {
	int ans=0;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(a[mid].tail<key) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}


dp方程
f[i]=max(f[i-1],f[lower_bound(1,i-1,a[i].head)]+a[i].tail-a[i].head+1);

于是就有了题解中最慢的代码(不确定吧)

#include<bits/stdc++.h>
using namespace std;

struct unit {
	int head,tail,val;
}a[150005];

int n;

int f[150005];

inline bool cmp(unit a,unit b) {
	return a.tail<b.tail;
}

inline int lower_bound(int l,int r,int key) {
	int ans=0;
	while(l<=r) {
		int mid=(l+r)>>1;
		if(a[mid].tail<key) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return ans;
}

int main() {
	scanf("%d",&n);
	for(register int i=1 ; i<=n ; ++i) {
		scanf("%d%d",&a[i].head,&a[i].tail);
		a[i].val=a[i].tail-a[i].head+1;
	}
	sort(a+1,a+n+1,cmp);
	for(register int i=1 ; i<=n ; ++i) {
		f[i]=max(f[i-1],f[lower_bound(1,i-1,a[i].head)]+a[i].val);
	}
	printf("%d",f[n]);
	return ~~(0^0);
}