在线决策单调性地皮还能单老哥分治做？

Register_int · 2025-08-03 11:33:18 · 算法·理论

原博客： 簡易版 LARSCH Algorithm noshi91。

众所周知决策单调性 dp 有很多做法，大家应该都会。但是主播主播，二分队列遇上要莫队算的贡献还是太菜了，整体二分还是太吃离线了，SMAWK 算法和 Wilber 算法又太吃常数和码量了。那么有没有什么常数小、能处理莫队、还好写的决策单调性优化 dp 呢？

有的兄弟有的，这就是我们要介绍的:

简易版 LARSCH 算法

设 dp 数组为 f。考虑分治。尝试设计一个 \operatorname{solve}(l,r) 函数。我们希望运行完这个函数后，f_{l+1\sim r} 的值都已经算对了。但是考虑分治中心 mid，我们如果要求 f_{mid} 一定要算对，那么 0\sim mid-1 的东西都要算对，这显然是不现实的。所以我们需要分成若干段考虑贡献。

具体地，我们在算 mid 时，不要求所有可能成为决策点的地方都算对了，而是要求 f_l 的决策点到 f_r 的大致决策点内的东西都算对了。我们需要：

• 只考虑 0\sim l 的话，r 的 f 值和决策点都算对了。

设 mid=(l+r)/2，那么我们需要做的事情是：

1. 把 l 的决策点到 r 的当前决策点之间的点转移到 mid，更新 f_{mid} 的值与决策点。
2. 递归 \operatorname{solve}(l,mid)。
3. 把 l+1 到 mid 之间的点转移到 r，更新 f_r 的值与决策点。
4. 递归 \operatorname{solve}(mid,r)。

然后我们就把所有 f 值算对了。

为什么？首先看第一步。由决策单调性，f_{mid} 在只考虑 0\sim l 时的决策点，必然在 f_l 的决策点与 f_r 的决策点之间，所以第二步的递归前提是满足的。第三步中，f_r 多考虑了 l+1\sim mid 的部分，因此第四步的递归前提仍是满足的。而对于最后一层的递归 \operatorname{solve}(k-1,k)，f_k 已经考虑了 0\sim k-1 的所有位置，因此运行结束后所有位置的 f 都算对了。

时间复杂度是多少呢？可以发现，对于分治的每一层，我们都相当于把所有点遍历了一遍，所以复杂度是 T(n)=2T(n/2)+\mathcal{O}(n)=\mathcal{O}(n\log n) 的。

当然该算法也有局限性。具体的，由于本算法对决策点进行了部分估计，在限制不够强时可能无法包含最优决策。因此 dp 的转移应当满足四边形不等式。

例题

wqs 二分使用例：[ABC355G] Baseball

设 dp_{i,j} 表示前 i 个位置放了 j 个点的方案数，则有