扫描、保留价值、单调栈。
最容易想到的是逐一扫描，然后看能不能通过当前点的相邻三个点得到该点答案，可惜无解。那么，就考虑对于某点来说，究竟需要那些信息才能给出答案。
容易想到，若给出当前行上每个列上方最邻近的沼泽地的位置，就足以给出答案，这一信息记为height[]，易知更新height[]代价不高，每进入一行更新一次height[]，最终等效于仅仅把所有点多扫描了一遍。
但是对于每个点枚举height[]代价太高，接下来考虑height[]中每个位置的保留价值，排除不需要保留的位置。
首先，对于某个点所考虑的height[]序列中，如果后面有一个比较低的，那它前面所有比他高的就都等价于削减到和它等高，这个削减不仅对当前点是必要的，对后续点也是必要的，削减之后，我们只需保留列数最小的那个，其余的对当前点没用，而且对后继点也没有用，没有保留价值。具体来说，在当前列向后推进一格时，height增加了一个，我们从后往前削减并丢弃。
如此排除，虽然去掉了一些无用项，但对于每个点仍需枚举得出答案，代价不够低。再考虑更深层次的保留。
如果按上述思路维护保留序列，那么保留序列的height是递增的，接下来考虑这每个保留位置之间谁更优，易知可用v=height-col的大小来衡量优劣，即越高、列数越小则越好。对于某个点所考虑的保留序列中，如果有位置在前而更优的位置，那么它后面比它差的位置对于该点无用，同时也对后续点无用，没有保留价值。所以，在当前列向后推进一格时，排除掉前面比它高的位置后，在比较比它低的第一个和它孰优孰劣，优则保留，劣则排除。
这里面理解上需要注意的一点是，在插入一个新位置时，我们总是假定这个序列是维护好了的。
这样一来，保留序列被维护成具有以下两个性质：1.仅排除了所有无保留价值的位置（即保留了所有可能的答案）。2.序列的最后一个位置就是最优解。
而根据上面叙述的维护方法，可知这个维护方法的代价不高，相当于仅增加了扫描的遍数。而且可以看出，保留序列实际上是一个单调栈，二重有序，高度单调、优势单调。
网友评论