DP 优化微剖 2

引言

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

书稿复制 - 问题引入

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

DP 思路

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

时间复杂度 .

单调性分析

容易感性证明以下引理

引理 1

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

那么对于原方程而言:

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

那么二分最近值就行啦

时间复杂度降为 .

单调性分析 2

上述二分其实是在两个离散函数上进行的(视 为常量):

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

那么考虑一下,如果 增加 呢?

引理 2

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

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

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

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

复杂度降为 .


  转载请注明: Sshwy's Blog DP 优化微剖 2

 上一篇
初等数论小结 初等数论小结
摘要 复习一下数论 符号的说明 大 符号:当且仅当存在正实数 和实数 ,使得 ,我们就可以认为,$f(x)=O(g(x
2019.01.26
下一篇 
[CQOI2011] 动态逆序对 [CQOI2011] 动态逆序对
题意给出一个 的排列 ,要求做 次删除操作,每次删掉一个数 ,求每次删除操作前整个序列的逆序对。 . 教训这道题告诉我永远不要相信 $
2019.01.24
  目录