DP 优化微剖 2

引言

和《鹰蛋》一样的优化思路

书稿复制 - 问题引入

对于长度为 的序列序列 ，要求将其分为 段，使得每一段的和的最大值最小

DP 思路

表示前 个数分 段的最小最大值，记 .

时间复杂度 .

单调性分析

容易感性证明以下引理

引理 1

显然少一个数总比多一个数好啊。。。

那么对于原方程而言：

• 关于 非严格单增
• 关于 非严格单减

那么二分最近值就行啦

时间复杂度降为 .

单调性分析 2

上述二分其实是在两个离散函数上进行的（视 为常量）：

然后 非严格单增，而 非严格单减，那么我们取两者最近值（近似看做交点）即为最大值的最小值

那么考虑一下，如果 增加 呢？

引理 2

显然，分得多总比分得少好啊。。。

那么当 自增时，相当于 会下降，而 会上升，那么他们的 “交点” 就会偏右

也就是说，最优决策点是非严格单调递增的

那就不用二分的过程了，直接顺便维护一下就行

复杂度降为 .