TouchStone
  Please Login
Login Sign Up
 Homepage  Problem Set  Examinations  Submissions  Discussions  Statistics
  • Home
  • Problem Set
  • P2273
  • Problem
  • P2273【HN09 day1】邪恶的大叔
    Limits : Time Limit : 10000 MS   Memory Limit : 565536 KB
    Description

    一个邪恶的大叔进入了这个神秘的空间,他发现这里有很多很多的Loli在这里,这个邪恶的大叔想把她们全部推倒!但是推倒Loli要耗费的体力太大了,所以他想用尽量少的次数把他们全部推倒。
       所有的Loli可以抽象成一个一维的坐标系,第i个Loli所在的位置为Xi,她的身高为Hi。大叔可以推倒任意个Loli让她们向左或者向右倒下去,第i个Loli倒下去之后可能会连带着别的Loli一起倒下去(向左倒就是在她左边并且满足|Xi-Xj|≤Hi的所有Loli也会一起向左倒,向右同样计算)。
       你的任务是帮助大叔计算出最少推倒多少个Loli可以让所有的Loli全部倒下。

    Input Format

    第一行一个整数N,表示Loli的个数。
      以下N行每行两个整数Xi Hi,分别表示第i-1个Loli的位置和她的身高。
      输入保证Xi递增输入。

    Output Format

    输出一行一个整数,表示大叔最少推倒的次数。

    Sample Input

    6
    1 1
    2 2
    3 1
    5 1
    6 1
    8 3

    Sample Output

    2

    Hint

    【样例解释】

       向右推倒第1个Loli可以让第2、3个Loli一起倒下。
       向左推倒第6个Loli可以让第5、6个Loli一起倒下。
    【数据约定】

       对于30%的数据,满足N≤10
       对于50%的数据,满足N≤1000
       对于100%的数据,满足N≤100000;Hi≤108;Xi≤231。