#include<iostream>
#include<algorithm>
using namespace std;
struct grass{
	int x,y;
}g[150001];
int n,f[150001];
bool cmp(grass a,grass b){
	return a.y<b.y;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>g[i].x>>g[i].y;
	sort(g+1,g+n+1,cmp);
	for(int i=1;i<=n;i++){
		f[i]=g[i].y-g[i].x+1;
		for(int j=1;j<i;j++){
			if(g[j].y<g[i].x) f[i]=max(f[i],f[j]+(g[i].y-g[i].x+1));
			else f[i]=max(f[i],f[j]);
		}
	}
	cout<<f[n];
}

乍一看题，切~不就一垃圾动归题吗，分分钟搞定的事！

#include<iostream>
#include<algorithm>
using namespace std;
struct grass{
	int x,y;
}g[150001];
int n,f[150001];
bool cmp(grass a,grass b){
	return a.y<b.y;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>g[i].x>>g[i].y;
	sort(g+1,g+n+1,cmp);
	for(int i=1;i<=n;i++){
		f[i]=g[i].y-g[i].x+1;
		for(int j=1;j<i;j++){
			if(g[j].y<g[i].x) f[i]=max(f[i],f[j]+(g[i].y-g[i].x+1));
			else f[i]=max(f[i],f[j]);
		}
	}
	cout<<f[n];
}

结果，有17个TLE……

花了一天时间去研究啊，发现可以优化一下，变成一段饲料的选或不选。如果选的话，与之相重复的饲料就不能选了，选与它没重复的吃；如果不选的话，选与它重复的吃。当然，这里不会有状态转移方程，因为我不会写因为大家也看不懂，我也就不写了。

代码如下（这不是正解！！）：

#include<iostream>
#include<algorithm>
using namespace std;
struct grass{
	int x,y;
}g[150001];
int n,f[150001];
bool cmp(grass a,grass b){
	return a.y<b.y;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>g[i].x>>g[i].y;
	sort(g+1,g+n+1,cmp);
	f[0]=0;
	for(int i=1;i<=n;i++){
		int j=i,num=g[i].y-g[i].x+1;
		while(!(g[j].y<g[i].x||j<1)) j--;
		f[i]=max(f[i-1],f[j]+num);
	}
	cout<<f[n];
}

上面这段代码之所以没全AC，是因为找第一个没与其重复的饲料段花了超长的时间，

浪费时间，浪费内存

后来想了想，感觉找第一个没与其重复的饲料段有点像二分，便用二分的方式优化了下代码：

#include<iostream>
#include<algorithm>
using namespace std;
struct grass{
	int x,y;
}g[150001];
int n,f[150001];
bool cmp(grass a,grass b){
	return a.y<b.y;
}
int two_fen(int l,int r,int x){
	while(l<r){
		int mid=l+r+1>>1;
		if(g[mid].y<x) l=mid;
		else r=mid-1;
	}
	return l;
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) cin>>g[i].x>>g[i].y;
	sort(g+1,g+n+1,cmp);
	f[0]=0;
	for(int i=1;i<=n;i++){
		int num=g[i].y-g[i].x+1;
		int j=two_fen(0,i-1,g[i].x);
		f[i]=max(f[i-1],f[j]+num);
	}
	cout<<f[n];
}

完成啦！芜湖！

良心题解，给个赞吧