题解

思路推导

按坐标从左向右考虑树。处理到第 $i$ 棵树时，之前所有树占据区域的最右端点已经确定。若 $x_i-h_i$ 严格大于这个端点，就可以把当前树向左砍倒；这不会比保留当前树更妨碍后续决策，因为两种选择的最右端点都是 $x_i$，而前者多砍倒一棵树。

若不能向左砍倒，再判断向右砍倒是否会碰到下一棵尚未处理的树。只有在 $i=n$，或 $x_i+h_i<x_{i+1}$ 时才能向右砍倒。若两种方向都不合法，只能保留当前树。

做法

维护已经处理部分的最右占据端点 last。依次扫描每棵树：优先尝试向左砍倒；否则尝试向右砍倒；若都不行则保留。每次按最终状态更新 last 并累计答案。

正确性证明

当向左砍倒合法时，它与保留当前树对后缀产生相同的边界 $x_i$，但答案多一，因此某个最优方案一定可以选择向左砍倒。

当向左不合法而向右合法时，当前树向右占据的区间严格停在下一棵树之前。之后的任何选择都只会处理坐标更大的树，因此这次砍倒不会破坏后缀可行性，并比保留多砍倒一棵。若两个方向都不合法，则任何可行方案都只能保留当前树。

由左到右对每一步应用上述交换论证，算法每次选择都能扩展为一个全局最优方案，最终答案最优。

复杂度分析

时间复杂度为 $O(n)$，空间复杂度为 $O(n)$（存储输入；也可流式实现为 $O(1)$ 额外空间）。