随机说话 2
stripe_python · · 个人记录
设指示函数
计数 dp 就是加法,最优化 dp 就是 chkmax/min。
平方做法一般显然。优化这种式子,本质是维护半在线数据结构,支持插点
常见的思路:
-
发现 dp 的妙妙性质然后神秘维护。
-
推式子发现
j 是一段前缀 / 区间,最优性 dp 用单调队列 / 树状数组 / 线段树优化,计数 dp 用前缀和优化。 -
以下只针对最优性 dp。
- 只有
(j,f_j) 凸包上的点可能有用。数据结构维护凸壳,斜率优化。 - 推式子发现
f_i 是关于f_j 的一次函数,李超树支持插入直线,求单点极值。 -
- 只有
-
-
根据性质直接维护。
-
-
-
- 各种各样的神奇性质,跟 dp 其实没啥关系了。
一般这种东西写代码的时候,都是维护辅助数组
g 关于j 的某些信息,先根据g 求f_i 再根据f_i 更新g 。这个g 就是所谓的半在线数据结构。 -