决策单调性

小 trick 不足挂齿。

考虑一个最优化分段 dp 状物 \(dp_i\gets \max\limits_{j=1}^{i-1}\{dp_j+w(j+1,i)\}\)，然而你只会 \(\mathcal O(nc)\) 转移，其中 \(c\) 是计算权值的复杂度。

这时候我们尝试使用决策单调性，也就是最终转移到 \(i\) 的 \(j\) 和最终转移到 \(i+1\) 的 \(k\) 始终有 \(j\leqslant k\)。

想发现是否有这样的性质也并不难。考虑到 \(i\) 的两条转移 \(dp_u+w(u+1,i)\) 和 \(dp_v+w(v+1,i)\) 且满足 \(u<v\)，你只需要保证存在性质 \(dp_u<dp_v\) 且后面那个东西的增量也满足 \(\Delta_u<\Delta_v\) 就行了。

然后就做完了。分 \(k\) 段的话就把 dp 数组变成 2D 的，然后尝试发现对于分相同段数存在决策单调性。

下面说说写法。

这东西绝不能双指针。虽然决策点的位置满足单调性，但是每个点上面的贡献完全不一定单调，所以双指针二分什么的都不行。

考虑分治。考虑拿下区间 \([1,n]\) 的中点 \(dp_{mid}\) 的转移点，显然可以 \(\mathcal O(nc)\) 取得，然后往两边分治，这样每次需要考虑的决策点折半，需要考虑的被转移点也折半，于是复杂度 \(\mathcal O(cn\log n)\)。