发现有时候还是会对各种优化比较混乱。
决策单调性
对于 \(i\) 来说,其决策点为 \(j\),那么对于 \(i'\ge i\) ,其决策点 \(j'\ge j\) 。
不存在依赖的可以直接分治,否则需要使用单调栈。
决策点的单调性
对于 \(i\) 来说,对于决策点 \(j\) 和 \(j'\) ,如果存在 \(j\le j'\) ,那么点 \(j\) 一定不劣于 \(j'\) ,反之亦然。
可以使用二分解决。
双指针
同时存在决策单调性与决策点的单调性。
可以直接用两个指针 \(l,r\) 来维护。
函数图像
有时候dp函数或转移函数可能存在某种规律。
如单峰函数,幂函数等,又或者函数存在单调性。
单调栈/单调队列
如果存在 \(i<j\) 使得点 \(j\) 比点 \(i\) 更优,那么点 \(i\) 就一定不会被选择。
如果对于决策点存在某些要求的话,则可以使用单调队列。
cdq分治
如果问题的形式是点 \(i\) 对点 \(j\) 有一个贡献,要求强制在线求每个点的值。
可以使用cdq分治去除强制在线的要求。
当然广义上的分治要更加复杂。
斜率优化
斜率优化有多种情况,不过一般来说是优化 \(dp_i=dp_j+a_i\times b_j+c_i+d_j\) 。也即转移中存在一些项同时与 \(i,j\) 有关。
显然可以先将与 \(i\) 有关的项提出来,与 \(j\) 有关的项全部合并。那么现在剩下的就是 \(a_i\times b_j+c_j\) 。
一般有两种做法,一种是将 \(-a_i\) 视为斜率,那么就相当于有许多点 \((b_j,c_j)\) ,希望找一个点使得截距最大/小。
还可以将 \(b_j\) 视为斜率,那么就相当于有许多线 \(y=b_jx+c_j\),求对于 \(x=a_i\) 的最大的 \(y\) 。
显然对于两种,我们都可以维护上/下凸壳。转移的点事实上以斜率形成了单调栈/队列。
因此,对于查询和修改值一样的,可以直接在单调栈/队列上做。否则可以在凸壳上二分。
对于修改位置不是单调的,就只能维护动态凸壳了。
当然使用李超线段树也是一种选择。
数据结构优化
显然如果存在某些性质则可以用数据结构优化。
需要注意的是分块可以做到优秀的复杂度。
根号分治
将大小小于根号与大于根号的分开讨论。
一般用于给定 \(n\) 个元素,总大小有限制的。