对于x<yx<yx<y,若 fyf_yfy 是 fi′f'_ifi′ 的最优决策点(即 fi′f'_ifi′ 由来 fyf_yfy 转移过来),那么对于 j>ij>ij>i ,xxx 绝对不会是 fj′f'_jfj′ 的最优决策点。
我们将其称为 决策单调性。
但是,理论上这应该是可以使用指针维护的;但是传统做法是分治一个 midmidmid 找到 fmid′f'_{mid}fmid′ 的决策点,并且向两边分治。
在校内碰到了一道题目,指针的写法并不能通过,数据太大不好分析;能否有谷民指出存在的问题。
万分感谢。