洛谷P1868 饥饿的奶牛
作者:
Air1222
,
2024-04-05 18:43:07
,
所有人可见
,
阅读 6
//本质为01背包问题
//f[i]表示选到第i个区间的最大值
//不选为f[i-1],选为f[第一个小于当前区间左端点的区间]+当前区间值(查找用二分优化)
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 1.5e5+10;
int f[N];
int n;
struct seg
{
int l,r,w;
bool operator < (const seg &w) const
{
return r<w.r;
}
}segs[N];
int t(int x)
{
int l=0,r=n;
while(l<r)
{
int mid=l+r+1>>1;
if(segs[mid].r<x) l=mid;
else r=mid-1;
}
return r;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>segs[i].l>>segs[i].r;
segs[i].w=segs[i].r-segs[i].l+1;
}
sort(segs+1,segs+1+n);
for(int i=1;i<=n;i++)
f[i]=max(f[i-1],f[t(segs[i].l)]+segs[i].w);
cout<<f[n];
return 0;
}