IDE
题库
题目列表
题单列表
题目收藏
记录
比赛
公开的比赛
我参与的比赛
用户
用户排名
奖牌排名
外部排名
近期排名
用户对比
用户组列表
博客
集训队
赛事新闻
赛事列表
获奖情况
视频列表
登录
选择围栏【模拟题】——高级
1 Sec
64 MB
|
Markdown
显示标签
一般
(*1600)
贪心
排序
动态规划
15
49
通过
提交
题目描述
给定 $n$ 个单位宽度木板,你的任务是用这些木板在一条直线上组成一个围栏,且木板之间不能互相覆盖。  这些木板非常特殊,第 $i$ 个木板必须被第 $i$ 个钉子固定,而第 $i$ 个钉子相对于原点的位置是给定的。你在钉子的左右移动,直到木板的边缘,因为钉子是没有宽度的,可以钉在木板的任何位置。
输入格式
第一行包含一个整数 $n$,表示有 $n$ 个木板。 接下来 $n$ 行,每行包含两个整数 $L_i, P_i$,分别表示第 $i$ 个木板的长度以及第 $i$ 个钉子的位置。 - $1 \le n \le 10000$ - $1 \le L_i, P_i \le 100000$
输出格式
一个整数,表示最多能选几个木板来组成围栏。
样例输入 #1
复制
7 5 9 2 17 6 10 3 11 2 16 4 13 5 6
样例输出 #1
复制
5
题面
提交
记录
统计
上一题
下一题
上传者
coach
创建时间
2012-10-29 12:50
修改时间
2023-09-07 14:57
Markdown 题面
×
登录
×
账号
密码
记住我