题目描述
有一条奶牛冲出了围栏,来到了一处圣地(对于奶牛来说),上面用牛语写着一段文字。
现用汉语翻译为:
有N个区间,每个区间x,y表示提供的x~y共y-x+1堆优质牧草。你可以选择任意区间但不能有重复的部分。
对于奶牛来说,自然是吃的越多越好,然而奶牛智商有限,现在请你帮助他。
输入输出格式
输入格式:
第一行,N,如题
接下来N行,每行一个数x,y,如题
输出格式:
一个数,最多能吃到的牧草堆数
输入输出样例
输入样例#1:
3
1 3
7 8
3 4
输出样例#1:
5
说明
1<=n<=150000
0<=x<=y<=3000000
题解:
我不会,太菜了,抄的题解;
f[i] 表示考虑到第i个区间的最大值;
f[i] = max(f[i-1],f[j]+len(i));
妥妥n^2我不会下面的了;
因为F肯定是单调不降的,所以我们找到第一个可以满足R[j] < L[i]的区间就可以转移;
于是二分...
我菜到想不到二分,大概是完了
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
#define ll long long
#define clear(a,x) memset(a, x, sizeof a)
int n;
struct date
{
ll L, R, len;
}da[];
ll f[]; inline bool cmp(date a, date b)
{
if (a.R == b.R) return a.L < b.L;
return a.R < b.R;
} inline int Find(int x)
{
int l = , r = x;
int ans = -;
while (l <= r)
{
int mid = l + r >> ;
if (da[mid].R >= da[x].L) r = mid - ;
else l = mid + , ans = mid;
}
return ans;
} int main()
{
scanf("%d", &n);
for (register int i = ; i <= n; i ++)
{
scanf("%lld%lld", &da[i].L,&da[i].R);
da[i].len = da[i].R - da[i].L + ;
}
sort (da + , da + + n, cmp);
clear(f, 0xcf);
f[] = ;
f[] = da[].len;
for (register int i = ; i <= n; i ++)
{
ll j = Find(i);
if (j != -) f[i] = max(f[i-], f[j] + da[i].len);
else f[i] = max(f[i-], da[i].len);
}
cout << f[n] << endl;
return ;
}