开学季大扫除,学校要把操场边一排旧栅栏清理掉。共有 N 块栅栏,按从左到右编号 1 \sim N,第 i 块立在数轴的整数位置 x_i 上(保证 x_1 < x_2 < \dots < x_N),高度为 h_i。
工人决定玩一个游戏:**每块栅栏最多推倒一次**——
- 向左推倒:占据区间 [x_i - h_i,\ x_i];
- 向右推倒:占据区间 [x_i,\ x_i + h_i];
- 也可以不推倒,只占着自己的点 x_i。
规则:任何两块栅栏**占据的区间不能重叠**(端点相触也算重叠;推倒的栅栏如果倒向某块立着的栅栏,也会压到它,同样不允许)。
求最多能推倒多少块栅栏。
第一行一个整数 N;
接下来 N 行,每行两个整数 x_i, h_i(x_i 严格递增)。
一行一个整数:最多能推倒的栅栏数。
3 1 2 2 3 5 1
2z
2 1 10 2 1
2
1 5 3
1
样例1说明:(第 1 块向左倒,占 [-1,1];第 2 块向左会压到第 1 块、向右([2,5])会压到第 3 块,只能立着;第 3 块向左倒,占 [4,5]。共 2 块。)
| t1 | 20 | N \le 8,x_i \le 30,h_i \le 6 |
| t2 | 20 | N \le 50,x_i \le 1000,h_i \le 100 |
| t3 | 20 | N \le 2000,x_i \le 10^6 |
| t4 | 20 | N \le 10^5,x_i, h_i \le 10^9 |
| t5 | 20 | N \le 10^5
| 时间限制 | 1 秒 |
| 内存限制 | 128 MB |