1 条题解
-
0
刷题去 LV 9 MOD @ 8 年前
- 1
信息
- 难度
- 10
- 分类
- (无)
- 标签
- (无)
- 递交数
- 10
- 已通过
- 0
- 通过率
- 0%
- 上传者
#include<cstdio>
#include<algorithm>
using namespace std;
struct data{
int x;
int y;
int z;
bool operator <(const data &oth) const
{
if(x<oth.x) return 1;
if(x>oth.x) return 0;
return y<oth.y;
}
}cow[100003];
int ef(int a,int b,int t)
{ if(a==b) {
if(cow[a].x>t)
return a;
return 0;
}
int mid=a+(b-a)/2;
if(cow[mid].x<=t) return ef(mid+1,b,t);
else return ef(a,mid,t);
}
int f[100004];
int main()
{
int b;
scanf("%d",&b);
for(int i=1;i<=b;i++)
{
scanf("%d%d",&cow[i].x,&cow[i].y);
cow[i].z=cow[i].y-cow[i].x+1;
}
sort(cow+1,cow+1+b);
f[b]=cow[b].z;
for(int i=b-1;i>=1;i--)
f[i]=max(f[i+1],f[ef(i+1,b,cow[i].y)]+cow[i].z);
printf("%d",f[1]);
return 0;
}