分治优化
概述
-
分治优化常常在 DP 的转移有某种单向单调性时使用，通过类似整体二分的结构，确保每个决策点只在一条链上出现，从而加速转移。一般这种分治优化也有对应的二分栈形式，区别仅在于逆推和顺推。此部分在四边形不等式优化一节。
-
分治优化本身还是一种非常有趣的 DP 实现方式。这一部分...我还不是非常了解，也是本节的重点。
CF1442D Sum
-
题意略。下面的复杂度分析里，因为
n,K 同阶，用n 代替K 。 -
发现这个就是把我们广义多重背包的物品反了过来，更短的转移反而“性价比”更高。考虑利用四边形不等式。
-
那么起式子，
dp_{i,j}=\max_{k\leqslant j}(dp_{i-1,k}+v_{i,j-k}) 。这里不写那种四边形形式了，容易看出，交叉小于包含。 -
当然 dp 的转移来源还是要推一下，盲猜有
k_{j-1}\geqslant k_j ，理由是取l<l'\leqslant r<r' ，假设有k_r=l,k_{r'}=l' ，推一下试试：-
-
左右消一下，得到
v_{r-l}+v_{r'-l'}\geqslant v_{r'-l}+v_{r-l'} ，显然和交叉小于包含矛盾了。
-
-
那完事了，
O(n^2\log) ？等等，我怎么觉得这个结论很反直觉？ -
令
j-1=0 ，则k_{j-1}=0 ，从而...从而......k=0 。显然不可能啊摔！ -
好吧，我们再仔细看看式子：上面的推导只能说明
dp_{i-1,l}+v_{r-l}+dp_{i-1,l'}+v_{r'-l'}\leqslant dp_{i-1,l}+v_{r'-l}+dp_{i-1,l'}+v_{r-l'} ，然而这一式子不能推出k_{j-1}\geqslant k_j ，其只是k_{j-1}\geqslant k_j 的必要条件。 -
...好吧。我们回到一开始的性价比，有一个直觉是这样的：只会有一组不选完，毕竟越选越划算，如果靠后的没选完的那一组更划算，则应该都选那组，否则都选这组。
-
形式化地说，设有两组物品
A,B 都没选完，不妨认为分别选了k_A,k_B 个，则：-
若
A_{k_A+1}\geqslant B_{k_B} ：放弃取B ，尽量取A ，显然不更劣。 -
若
A_{k_A+1}<B_{k_B} ：这代表着A_{k_A}<B_{k_B} ，于是放弃取A ，尽量取B ，显然更优。
-
-
OK！那么这样一来，除了我们钦定的那一组之外，都变成
01 背包了，要么不选要么选完。然而...暴力枚举哪一组不选完？组内的 dp 容易预处理，毕竟就是前缀和；然而即使我处理好前后缀 dp，这一部分的复杂度是O(n^2) ，把三个背包暴力合到一起...虽然合两个其实就够了（第二次不用合，因为只关心dp_K ），但O(n^2) 做n 遍，还是暴力复杂度啊。 -
解法 1：分块。
-
分
B 个块，暴力枚举不选完的在哪个块里，合并前后缀 DP 或直接暴力 DP 一遍，反正都是O(n^2) 。 -
在块内暴力枚举哪个没选完，将其他的物品暴力转到刚才的背包里，
O(\frac{n}{B}(\frac{n}{B}n)) 。 -
暴力枚举没选完的选了几个，计算对应情况下选
K 个的最大总价值，O(n) 。 -
故总复杂度为
O(B(n^2+\frac{n}{B}(\frac{n^2}{B}+n)))=O(Bn^2+\frac{n^3}{B})=O(n^2(B+\frac{n}{B})) ，取B=\sqrt{n} ，复杂度为O(n^2\sqrt{n}) 。 -
够过了，虽然纸面
5\times 10^8 ，但背包常数小。
-
-
解法 2：分治。
-
考虑用二分树。怎么到处都是二分树！也许该叫分治树？
-
令初始区间为
[1,n] ，先考虑key\leqslant mid 的情况，key 为不选完的一组，此时将[mid+1,r] 的物品转进背包得到左子区间的背包，回溯时再考虑key>mid ，将[l,mid] 转进背包。 -
即我们维护的背包其实是“除了当前区间外的全局背包”。可以看出，同时只需要维护一条链上的
\log 个背包（转移完毕的就好），每一层都将所有物品转移一次，空间回收的复杂度因为分治树只有O(n) 个点所以是O(n^2) ，故总复杂度O(n^2\log) 。 -
妙哉！
-