TouchStone
  Please Login
ログイン 登録
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P2273
  • 問題
  • P2273【L1 SOLO 第七场 HN09 day1】邪恶的大叔
    制限 : 時間制限 : 10000 MS   メモリ制限 : 565536 KB
    問題説明

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

    入力形式

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

    出力形式

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

    サンプル入力

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

    サンプル出力

    2

    ヒント

    【样例解释】

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

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