CF868F是一个

cirnovsky · 2021-09-25 14:46:08 · 个人记录

link。

值域分治优化决策单调性 DP 的 trick。朴素做法 trivial，不赘述。

考虑求取一个区间 [l,r] 的 DP 值。先搞定在 m=\lfloor\frac{l+r}{2}\rfloor 的 DP 最优决策点，由于决策的单调性，[l,m) 和 (m,r] 的最优决策点就在 [l',m'] 和 [m',r']（' 系列变量代表最优决策点）。

于是值域分治解决。

特征码 cf868f。