[LUOGU1868]|[LUOGU1868] 饥饿的奶牛 - dp二分 [LUOGU1868]饥饿的奶牛-dp二分

题目描述有一条奶牛冲出了围栏，来到了一处圣地（对于奶牛来说），上面用牛语写着一段文字。
现用汉语翻译为：
有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]的区间就可以转移；
于是二分...
我菜到想不到二分，大概是完了

【[LUOGU1868]|[LUOGU1868] 饥饿的奶牛 - dp二分】

#include #include #include #include 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[150010]; ll f[150010]; 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 = 1, r = x; int ans = -1; while (l <= r) { int mid = l + r >> 1; if (da[mid].R >= da[x].L) r = mid - 1; else l = mid + 1, ans = mid; } return ans; }int main() { scanf("%d", &n); for (register int i = 1; i <= n; i ++) { scanf("%lld%lld", &da[i].L,&da[i].R); da[i].len = da[i].R - da[i].L + 1; } sort (da + 1, da + 1 + n, cmp); clear(f, 0xcf); f[0] = 0; f[1] = da[1].len; for (register int i = 2; i <= n; i ++) { ll j = Find(i); if (j != -1) f[i] = max(f[i-1], f[j] + da[i].len); else f[i] = max(f[i-1], da[i].len); } cout << f[n] << endl; return 0; }

转载于:https://www.cnblogs.com/BriMon/p/9262598.html