理论知识

整体二分优化递推

注意用词，这里的式子大概是 \(f_{i}=g_{j}+w(i,j)\) 的形式，那么如果能满足 \(g\) 是预先知道的值且使得 \(f_{i_1}\) 和 \(f_{i_2}\)（\(i_1<i_2\)）取到最优值的点 \(j_1j_2\) 满足 \(j_1\le j_2\)，那么我们称这个式子有决策单调性。

考虑因为单调性，可以用整体二分进行优化。

数列切割

传送门

考虑一个朴素的式子 \(f_{i,k}=\min(f_{j,k-1}+w(j+1,i))\)，发现当我们每轮计算所有 \(k\) 的时候 \(f_{j,k-1}\) 是已知的。