menu 大连理工大学 DP·AC算法竞赛协会 ICPC集训队 Online Judge
account_circle 请登录
home
首页
book
题目
library_books
题单
apps
分类
play_circle_outline
状态
layers
竞赛/作业
equalizer
排名
assignment_ind
登录
person_add
注册
1082: [USACO 2006 Ope B]Cows on a Leash
时间限制:1.000s
内存限制:128MB

题目描述

给定如图所示的若干个长条。你可以在某一行的任意两个数之间作一条竖线,从而把这个长条切开,并可能切开其他长条。问至少要切几刀才能把每一根长条都切开。样例如图需要切两刀。

注意:输入文件每行的第一个数表示开始的位置,而第二个数表示长度。

输入格式

Line 1: A single integer, N(2 <= N <= 32000)
Lines 2..N+1: Each line contains two space-separated positive integers that describe a leash. The first is the location of the leash's stake; the second is the length of the leash.(1 <= length <= 1e7)

输出格式

Line 1: A single integer that is the minimum number of cuts so that each leash is cut at least once.

样例输入 content_copy

7
2 4
4 7
3 3
5 3
9 4
1 5
7 3

样例输出 content_copy

2

分类