算法小站
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
首页
wiki
新鲜事
文章搜索
网站导航
回忆录
登录
注册
算法基础
搜索
数据结构
字符串
数学
图论
动态规划
计算几何
杂项
wiki 主题
算法基础
二维偏序
高维前缀和
树上差分
中位数定理
搜索
数据结构
线段树
线段树单点修改
线段树区间修改
动态开点线段树
线段树的合并(一)
可持久化线段树
树链剖分
平衡树
FHQ-Treap
珂朵莉树
分块
位分块
根号分治
虚树
字符串
回文串
回文树
数学
组合计数
二项式定理
生成函数(一)
FFT
多项式与形式幂级数
同余与模
同余与模的应用
同余与模的概念
特殊的数
斯特林数
斯特林数相关的恒等式
斯特林数的综合应用
FFT的应用
整除分块
图论
图的连通性
有向图的强连通分量
无向图的割点割边和双连通分量
流和匹配
最大流
最大流的一些应用
图论杂项
最大团搜索算法
树上问题
kruskal重构树
kruskal重构树的一些问题
动态规划
背包模型
dp优化
凸壳优化
单调队列优化
计算几何
杂项
启发式合并
高精度
一些经典问题
约瑟夫环
曼哈顿距离
多重集合的排列组合
蔡勒公式
排列与置换
Catalan数与格路径
主题名称
是否为父主题
是否为其添加wiki文章
取 消
确 定
选择主题
修改主题名称
修改父主题
修改wiki文章
取 消
删 除
修 改
算法基础
搜索
数据结构
字符串
数学
图论
动态规划
计算几何
杂项
动态规划
背包模型
dp优化
凸壳优化
单调队列优化
[[ item.c ]]
0
0
凸壳优化
## 凸壳优化初步 形如转移方程 ```math \displaystyle dp(i, j) = \max_{j' \in [l, r]} \{ dp(i-1, j') + K(i)X(j) \} ``` 有一项和$$i$$有关又与$$j$$有关的项,这个时候考虑凸壳优化,怎么去切入思考呢? 首先可以考虑的是,只关心$$dp_i(j)$$,只研究$$i$$这个阶段的状态,看看关于$$j$$有没有凸性 ### 凸壳优化举例 **[E. Kevin and And](https://codeforces.com/contest/2061/problem/E)** **问题描述** 给你一个长度是$$n$$的序列`a[1...n]`和长度为$$m$$的序列`b[1...m]`,你可以执行最多$$k$$次操作 每次操作,你可以选择$$(i, j)$$,令`a[i] &= b[j]`,最多`k`次操作下来,问$$a$$序列的和最小是多少? **算法分析** > 首先不难写出一个朴素的`dp` 由于$$m$$很小,我们可以暴力打表,`table(i, k)`表示对$$a_i$$应用$$k$$次操作,能得到最小的数是多少? 暴力枚举$$|B|$$中大小是$$k$$的子集,对每个$$i$$求出`table(i, k)`即可 那么可以写出一个朴素的$$dp$$方程 ```math dp(i, j) \xleftarrow{\min} dp(i-1, j') + table(i, |j - j'|), \quad |j - j'| \leqslant K ``` 其中$$dp(i, j)$$表示考虑前$$i$$个数,用了$$j$$次操作,能够得到的最小的和 枚举在$$i$$上浪费了多少次操作,类似背包,这样做的时间复杂度是$$O(n^2m^2)$$ 因为你需要枚举$$i, j, j'$$ > 考虑凸性 
看完文章有啥想法
发布评论
目录
[[ item.c ]]
43 人参与,0 条评论