[心之碎片] - DP优化专题
本帖最后由 柿子饼同学 于 2024-7-22 09:46 编辑DP优化的两个思路: 优化状态本身和优化转移方式{:10_243:}
优化转移方式的一些考虑方向{:10_277:}
前缀/后缀 max/min/和... (看状态转移, 有一题用的是对角线前缀)
费用提前计算 (一些附加的东西会影响后面的所有东西, 那就可以直接提前算过来, 压掉一维)
填表法还是刷表法 (要注意转移的顺序)
各种数据结构
状压, 矩阵优化
对于一个柿子一定要有分离变量的意识, 把与 i 有关 与 j 有关的变量分出来, 看看能不能辅助转移
优化状态本身{:10_245:}
去掉冗余状态(比如这个维度可以通过状态里别的数值算出来)
互换状态 例如 f(x) = y, 发现 x 的范围非常大, 但是 y 非常小, 可以看看能不能用一些手段变成 g(y) = x
朴素的状态应该是 f(x, y, ...) = 0/1 这个状态是否可行, 那这时候就要看看能不能把状态里的一维作为状态的答案
必须注意: 下标不要写错写反, 矩阵快速幂是单位矩阵不是全1, 矩阵注意乘了多少次方
===下面有几个需要专门学的优化方式
决策单调性{:10_254:}
决策单调性指的是, 如果 j 是 i 的最优决策, 那随着 i 变化, j 也会单调的变化
斜率优化
对于这类 DP 问题我们有几种不同的视角去看待
举个栗子 - 序列分割
你正在玩一个关于长度为 n 的非负整数序列的游戏。这个游戏中你需要把序列分成 k+1 个非空的块。
为了得到 k+1 块，你需要重复下面的操作 k 次：
选择一个有超过一个元素的块（初始时你只有一块，即整个序列）
选择两个相邻元素把这个块从中间分开，得到两个非空的块。
每次操作后你将获得那两个新产生的块的元素和的乘积的分数。你想要最大化最后的总得分。
容易得出方程: f(a, b) 表示前 a 个数分成 b 段的最大得分, 则 f(a, b) = max(f(k, b - 1) + s*(s - s)), 其中 s 是前缀和
下面我们来优化它
方法 1 - 分离变量然后用单调队列优化
假设 有 x1, x2 , 在 a 这个点上 x1 比 x2 更优, 那可以得出一个不等式
f(x1, b - 1) + s*(s - s) > f(x2, b - 1) + s*(s - s)
把带 i 的放在一边, 得到了
s > .../...(不想写了...)
设 右边的那个是 g(x1, x2), 左边的是 h(a)
然后发现 h(a) 单调递增, 但是 g(x1, x2) 是定值
###补档
就是 只和 i 有关的项和常数 放在一边, 设成 h(i) , 别的放另一边构成 g(j1, j2)
这里的柿子告诉我们如果 j2 优于 j1, 那么 h(i) > g(j1, j2)
推出:
h(i) < g(j1, j2) 时, j1 优于 j2, = 时, j1 和 j2 一样
那么怎么加点进来呢?
如果我们有 g(j1, j2) > g(j2, j3) , 那么 j2 一定不是最优决策, 把 h(i) 的值分类 3 种情况即可
我们维护这些 j , 然后如果 h(i) 不是单调那么久不在左边删点, 每次二分一个位置即可
为什么要二分找第一个呢 , 因为 g(j1, j2) , g(j2, j3) , g(j3, j4)... 如果这些都大于 h(i) , 那选择 j3 的话发现 j2 优于 j3, 这样...
###
所以 h(a) 一定在某一个时刻一旦超过 g , 那以后也超过 g
尝试用单调队列维护所有的 x , 如果 g(x1, x2) > g(x2, x3) 那 x2 就没有用了, 删去即可 , 然后加入新的 x
方法 1 总结: 在可以分离变量把柿子变成 g 和 h 的那种形式考虑这样的优化 ( h 可以不单调, 在队列中二分即可, 但是我们想让 g 单调不然不行)
for 每个m
初始化队列 l=r=1, j=0
for 每个i
while l+1<=r and h(i) > g(j,j) l++
使用j作为决策点，计算dp
while l+1<=r and g(j,j) > g(j,i) r--
j[++r]=i
方法2 - 斜率优化, 把柿子看成一次函数(关于 i 的)
变成这样的形式 Fj(i) = A(j) * i + b(j), 这样, 每个 j 相当于提供了一个函数 (也可以不是一次函数, 需要保证当 j1 超过 j2 以后, j1 不会小于 j2)
Aj bj 只和 j 有关,
用单调队列维护这些函数, 对于当前的 i , 如果 Fj 和 Fj-1 的交点小于 i 那么 Fj-1 就没用了, 删掉
struct Line {int a, b}; Line q[]; // q[]里的元素代表直线 a+bx
for 每个m
初始化队列 l=r=1, q为j=0代表的直线
for 每个i
while (l+1<=r and C(i) > q和q交点的x坐标) l++
使用q作为决策点，计算dp=q.a+q.b*C(i)
Line lnew = i作为决策点所代表的直线 A(i)+B(i)*x
while (l+1<=r and
q和q交点的x坐标 > q和lnew交点的x坐标) r--
q[++r]= lnew
当你写出来之后你就会发现程序和上面使用纯代数推导写出的程序是完全等价的
事实上，对本题而言，g(j1,j2)就是此处队列q[]里相邻两条直线交点的x坐标h(i)就是C(i)
方法3 - 斜率优化, 把柿子看成两点斜率式
这样就用单调队列维护凸壳即可, 每次看中间的点有没有用
方法4 - 看每个 j 是哪一段区间的最佳转移点, 用队列维护
对于某两个 j1<j2，如果在某个 i 处 j2 比 j1 优，那么在更大的 i 处 j2 也一定比 j1 优 (我们称满足这个条件为强决策单调性)
由此可以推出随着 i 增大，最优决策点也非严格单调增 (我们称满足这个条件为弱决策单调性)
绝大多数情况题目满足弱的就满足强的, 不用太在意 (二分队列做法需要满足强的, 分治做法只需要满足弱的)
单调队列做法
总的来说就是对于每个 j 确定她掌管的区间, 替换以前的 j
尝试维护只考虑 间的所有决策点 j，所构成的所有最优决策区间
struct OptInfo{int j,l,r;};
q[]初始化为
head=tail=1
q.j=0, q.l=1, q.r=n
为了维护以后的 的最优决策点区间划分，我们将保证
对于 head<=x<=tail-1，有
q.j < q.j
q.r+1 == q.l
q.l<=i
q.r==n
假如q[]已经算好了，我们该如何计算i的答案？
若 i > q.r，那么q.j 以后也不会再有机会了，所以左侧出队 head++。并重复以上过程
以上过程结束后，我们会发现
q.l <= i <= q.r
那么 q.j 就是最优决策点，用j来计算答案
现在i作为一个新的可用的决策点进来了，我们该如何维护q[]?
为了避免混淆，记 jnew = i
如果在 n 上 jnew 没有 q.j 好，那就意味着 jnew 不会在任何时候成为最优决策点
“到最后 jnew 都没超过 q.j，那中间更不可能”
此时放弃将 jnew 加入队列，q[]不变
如果在 q.l 上 jnew 比 q.j 好，那就意味着 q.j 一直会被后来者 jnew 超越，
tail--; q.r = n;
继续看下一个 q
如果队列为空了，那么 q[++tail]={jnew, 1, n}
如果在 q.l 上 jnew 没 q.j 好，但是在n上 jnew 比 q.j 好
那就意味着原本的 .l, n] 将会被瓜分为两部分
我们需要找到一个切分点，在这个切分点前 q.j更优，这个切分点之后 jnew 更优。设这个切分点为 x
q.r = x; q[++tail]={jnew, x+1, n};
如何找到切分点？
在 .l, n] 上二分！
分治做法
先计算左区间, 然后用左区间更新右区间, 然后计算右区间
一般类型是 f(i) = max(f(j) +,,,) 的 一维 dp
把约束条件转换为偏序问题即可
矩阵加速递推{:10_256:}如果发现是一个递推柿子, 而且要算的项很大, 考虑矩阵快速幂优化一下
例题{:10_258:}
决策单调性/斜率
P3648 序列分割
P3299 保护出题人
P3515 Lightning Conductor
矩阵
Decoding Genome
Product Oriented Recurrence
数据结构
Partition Game
遇到 abs 想着打开分类讨论, 对角线前缀和
Maximum Monogonosity
状态的一维过大可以尝试把状态和答案互换
Brand New Problem
Complexity
哎, 真难调{:10_266:}{:10_250:}{:10_301:}{:10_327:}{:10_265:}
{:9_227:}{:9_230:}{:9_234:}{:9_237:}{:9_231:}
先顶后看，良好习惯 中英文泡椒 发表于 2024-7-19 19:21
先顶后看，良好习惯
感谢资瓷~ 还是矩乘和数据结构优化更适合我 zhangjinxuan 发表于 2024-7-19 19:28
还是矩乘和数据结构优化更适合我
太难调了, 一道题能搞半天{:10_266:} 柿子饼同学 发表于 2024-7-19 19:54
太难调了, 一道题能搞半天
不如写数据结构清心 先顶后看，良好习惯 不懂帮顶{:10_254:} 顶 顶 佬 {:10_275:} 拿币 顶了，定了，知识点好密集啊 {:7_113:}
页:
[1]