给n棵树的在一维数轴上嘚坐标以及它们的高度。现在要你砍倒这些树砍倒的树不能重合、当然也不能覆盖另外的树原来的位置,现在求最大可以看到的树的數目
网上有很多人说这是DP然而我怎么看都不需要用到DP。首先题中数据是按照坐标从小到大给出的那我们直接从左到右每棵树依次看,那么显然可以有以下几点
- 最左边那棵树一定可以向左倒最右边那棵树一定可以向右倒
- 每棵树,能向左倒就向左倒(向左倒了後就不会影响下一棵)
- 每棵树,能倒就倒(每棵树向哪个方向倒或者倒不倒,只受影旁边两棵树的影响那么这棵树倒不倒只会影响到祐边一棵树,绝不会传递给后一棵的决策)
那么很显然这是贪心……按照这个思路,我们甚至可以边读入数据边处理具体见下面的代碼: