/ Vijos / 题库 /

推倒骨牌

推倒骨牌

时间限制:1秒  内存限制:256M


【题目描述】

  给出 \(n\) 个多米诺骨牌的 \(X\) 坐标以及高度 \(H\),每次你可以选任意一张向左推或向右推,推倒后,会产生连锁反应。也就是说,如果 \(|X[i]-X[j]| <= H[i]\),如果 \(X[i] > X[j]\),则把i向左推倒后,则 \(j\) 也会被推倒,如果 \(X[i] < X[j]\),则把 \(i\) 向右推倒后,\(j\) 也会被推倒。连锁反应是指 \(j\) 倒掉后,凡是在 \(j\) 倒向的方向上能推倒的骨牌,也会推倒,他们倒掉,又会推倒他们够的着的骨牌……。

  现在问最少几次就能把所有的骨牌推倒。

【输入格式】

  第一行一个整数 \(n\),表示骨牌数量。接下来的 \(n\) 行,每行包含两个整数 \(X[i],H[i]\),表示第 \(i\) 个骨牌的位置和高度。

【输出格式】

  一行一个整数,表示推的最少次数。

【输入输出样例】

 Input

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

 Output

2

【数据限制】

  \(100\%\) 的数据满足:\(1≤n≤100000\),\(1≤X[i]≤2^{31}-1,\)0≤H[i]≤10^8$。

【来源】

  Mr.he

信息

ID
2557
难度
(无)
分类
动态规划 | 数据结构 | 线段树 点击显示
标签
(无)
递交数
0
已通过
0
通过率
?
被复制
1
上传者