题意:
给出一列数,满足b1 ≤ b2 ≤ ... ≤ bx ≥ bx + 1 ≥ bx + 2... ≥ bk的子段为Ladder.
给出一系列询问, 判断该子段是否构成Ladder.
思路:
朴素地想:
对于一个询问, 向右扫描,
若一直不减, yes.
若遇到第一个减少项, 则记录其前驱, 看此后是否一直不增. 若是, yes. 否则,no.
这样的话, 最多是O(n*m)的...1e10的数量级, 超时...
注意到询问是动态的, 而数列是静态的. 可以预处理, 记录下数列的性质, 查询的时候直接调用即可. 这里就用到了dp记忆化搜索...
首先考虑需要记录的性质是什么.
判断是否是ladder需要知道的信息是什么?
......
阅读全文