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

/*
a[i][0]表示i位置是否为某一区间的起点
a[i][1]表示以i为起点的区间的价值
f[i]表示到i位置的最大价值是多少
因为不允许区间重叠,所以一旦选了某个区间,其他的价值只能来自这个区间之外
考虑从前往后进行状态转移
那么f[i+a[i][1]]=max{f[i]+a[i][1]} 其中i必须保证是区间i的起点
*/
#include<iostream>
#include<cstdio>
using namespace std;
int n,a[][],r,f[];
int main(){
scanf("%d",&n);
int x,y;
for(int i=;i<=n;i++){
scanf("%d%d",&x,&y);
a[x][]=;a[x][]=y-x+;
r=max(r,y);
}r++;
for(int i=;i<=r;i++){
f[i]=max(f[i],f[i-]);
if(a[i][]){
f[i+a[i][]]=max(f[i+a[i][]],f[i]+a[i][]);
}
}
printf("%d",f[r]);
}

最新文章

  1. Python Day17
  2. java.sql.SQLException: ORA-00972: 标识符过长
  3. 01WebApi防篡改机制---HMAC机制
  4. php 判断复选框checkbox是否被选中
  5. js运动:多div变宽、二级菜单
  6. 启动和JQuery绑定--AngularJS学习笔记(二)
  7. beta阶段140字评论
  8. Android之jni入门
  9. Oracle横向纵向汇总
  10. Struts2的crud
  11. 30大最有影响力的Web设计与开发英文博客
  12. linux中proc文件系统 -- ldd3读书笔记
  13. 详解Java解析XML的四种方法
  14. NetAnalyzer笔记 之 一. 开篇语
  15. 测试部署nginx
  16. [补档][JLOI 2017]聪明的燕姿
  17. Java的绝对路径和相对路径
  18. 自动化测试用例getText()获取某一个元素的值返回null或空
  19. MT【312】特征根法求数列通项
  20. Django ----- 模板2

热门文章

  1. JS表自动取值赋值
  2. testng ITestListener使用
  3. node版本管理工具 -- nvm安装与使用
  4. uboot 从sd卡加载文件并烧写到nand flash
  5. MVC+Ext.net零基础学习记录(五)
  6. mooc_java 集合框架中 学生所选课程2Map&amp;HashMap
  7. POI2014
  8. 1119 Pre- and Post-order Traversals(30 分)
  9. ACM学习历程——POJ3468 A Simple Problem with Integers(线段树)
  10. Java网络与多线程系列之1:实现一个简单的对象池