首页 > 代码库 > 动态规划 洛谷P1868 饥饿的奶牛
动态规划 洛谷P1868 饥饿的奶牛
P1868 饥饿的奶牛
题目描述
有一条奶牛冲出了围栏，来到了一处圣地（对于奶牛来说），上面用牛语写着一段文字。
现用汉语翻译为：
有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
我太菜了......难受
第一遍写了个zz的贪心，刚写完就发现错误了
第二遍二维动归，迷之错误，现在我仍然不知道为什么二维是错的
第三遍改邪归正，老老实实地瞎写......
记录几句毒鸡汤：
1.别学了，退役吧
2.高考都这么菜，退役吧
3.下学期就省赛了，你连这水题都不会做，退役吧
4.待更新......
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 using namespace std; 6 int n,ans; 7 struct data{ 8 int x,y,len; 9 }node[2000010]; 10 int f[4000010]; 11 bool cmp(const data&aa,const data&bb){ 12 return aa.y<bb.y; 13 } 14 int main(){ 15 scanf("%d",&n); 16 for(int i=1;i<=n;i++){ 17 scanf("%d%d",&node[i].x,&node[i].y); 18 node[i].len=node[i].y-node[i].x+1; 19 } 20 sort(node+1,node+n+1,cmp); 21 for(int i=1;i<=n;i++){ 22 for(int j=node[i].y-1;j>=0;j--){ 23 if(f[j]) break; 24 f[j]=ans; 25 } 26 f[node[i].y]=max(f[node[i].x-1]+node[i].len,ans); 27 ans=max(f[node[i].y],ans); 28 } 29 printf("%d",ans); 30 return 0; 31 }
动态规划 洛谷P1868 饥饿的奶牛
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。