/ Vijos / 题库 /

选择围栏

选择围栏

背景

2009NOIP余姚中学内部暑期集训
7月14号模拟赛第二题

描述

给定n个单位宽度木板,你的任务是用这些木板在一条直线上组成一个围栏,且木板之间不能互相覆盖。

这些木板非常特殊,第i个木板必须被第i个钉子固定,而第i个钉子相对于原点的位置是给定的。你在钉子的左右移动,直到木板的边缘,因为钉子是没有宽度的,可以钉在木板的任何位置。

格式

输入格式

给定n,表示有n个木板n<=10000。

接下来n行,每行2个整数 Li and Pi (1 <= Li, Pi <= 100000),表示第i个木板的长度,以及它必须被固定在第i个钉子的位置。

输出格式

输出最多能选几个木板,组成围栏

样例1

样例输入1

7
5 9
2 17
6 10
3 11
2 16
4 13
5 6

样例输出1

5

限制

各个测试点1s

提示

5
30%的数据 n<=100;
100%的数据n<=10000;
木板的左端点可以为负

信息

ID
1575
难度
6
分类
动态规划 点击显示
标签
递交数
441
已通过
111
通过率
25%
上传者

相关

在下列训练计划中:

RP++分类题库