暴力 dp 是很拉跨的，我们会设 \(dp_{i,j}\) 表示前 \(i\) 个 \(a_i\) 分裂后，最后一个 \(b\) 为 \(j\) 时的最小答案，爆炸。
但这里面有很多性质啊，直观地我们可以感受到，若已经确定了决策 \(dp_{i-1,k}\)，那么无论如何选择 \(a_i\) 的分裂方式，对答案带来的贡献都会在 \(0\sim 2\) 之间，即，当前决策的影响是很弱的。
并且我们发现，如果存在一个可能更加优秀的非最优决策，也最多只能额外达成和 \(b_{2i-1}\) 贴合的 \(1\) 的贡献，即，之前的最优状态一定可以作为最优决策。（像是更强的最优子结构性质）
上面这条性质太核心了。
所以我们考虑能否维护每一轮 dp 之后的最优状态集合。
假设我们已经拿到了前 \(i-1\) 轮 dp 结束后的最优决策集合，思考第 \(i\) 轮 dp 的具体贡献。
- 若 \(a_i\) 为偶数，此时 \(a_i\) 拆分的贡献只为 \(0/1\)。
- 若最优决策集合内存在 \(\frac{a_i}{2}\)，可以达成贡献 \(0\)，此时新最优决策集合增加 \(\frac{a_i}{2}\)。
- 否则一定无法达成贡献 \(0\)，最优贡献一定为 \(1\)：
- 一定可以有新最优决策 \(\frac{a_i}{2}\)。
- 对于最优决策集合内所有 \(p<a_i\) 的决策 \(p\)，都可以使得新最优决策集合增加 \(a_i-p\)。
- 若 \(a_i\) 为奇数，此时 \(a_i\) 拆分的贡献只为 \(1/2\)。
- 若最优决策集合内存在 \(p<a_i\) 的决策 \(p\)，都可以达成贡献 \(1\)，新最优决策集合增加 \(a_i-p\)。
- 否则只能达成贡献 \(2\)，此时 \(a_i\) 可以随意拆分，新最优决策集合增加决策 \([1,a_i)\)。
我们发现每轮 dp 后的最优决策集合相比上轮，可能会加一个值，可能会将一些数 \(\times (-1)+a_i\) 后把剩下的数删掉，也可能会把集合变成一个值或一个区间，故维护系数 \(k,b\)，表示集合内实际维护的是 \(kx+b\)，该清空就清空，即可做到 \(O(n\log n)\) 的时间复杂度。
若上一层的最优状态一定可以作为下一层的最优决策，可以考虑直接对最优决策集合进行维护。