安阳如何建立自己的网站平台,网站建设策划实施要素,泉州做网站工资,iis6cgi php网站缓存原题
题目描述
有一条奶牛冲出了围栏#xff0c;来到了一处圣地#xff08;对于奶牛来说#xff09;#xff0c;上面用牛语写着一段文字。
现用汉语翻译为#xff1a;
有 N 个区间#xff0c;每个区间x,y 表示提供的x∼y 共y−x1 堆优质牧草。你可以选择任意区间但不…原题
题目描述
有一条奶牛冲出了围栏来到了一处圣地对于奶牛来说上面用牛语写着一段文字。
现用汉语翻译为
有 N 个区间每个区间x,y 表示提供的x∼y 共y−x1 堆优质牧草。你可以选择任意区间但不能有重复的部分。
对于奶牛来说自然是吃的越多越好然而奶牛智商有限现在请你帮助他。
输入格式
第一行一个整数 N。
接下来 N 行每行两个数x,y描述一个区间。
输出格式
输出最多能吃到的牧草堆数。
输入输出样例
输入 #1
3
1 3
7 8
3 4
输出 #1
5
说明/提示 解题思路
动态加二分。
构造一个结构体存储元素然后按照r从小到大排序。
dp[i]max(dp[i-1],dp[lower_bound(1,i,cow[i].l)]cow[i].val)
lower_bound(二分查找) 最后一个没有和cow[i].l相交的元素寻找到后取最大的那个区间。
AC代码
#includeiostream
#includealgorithm
using namespace std;
const int N1.5e55;
struct Cow{int l,r;int val;bool operator (const Cow b){return rb.r;}
}cow[N];
int n,dp[N];
int lower_bound(int l,int r,int k){int ans0;while(lr){int mid(lr)1;if(cow[mid].rk) {ansmid;lmid1;}else rmid;}return ans;
}
int main(){scanf(%d,n);for(int i1;in;i){scanf(%d %d,cow[i].l,cow[i].r);cow[i].valcow[i].r-cow[i].l1; }sort(cow1,cown1);for(int i1;in;i){dp[i]max(dp[i-1],dp[lower_bound(1,i,cow[i].l)]cow[i].val);}printf(%d,dp[n]);return 0;
}
