前置芝士 单调队列优化 DP
⌈ 写不动数据结构呜呜呜，先来补这个 ⌋
对于一个 DP，我们想优化祂的 ⌈ 转移 ⌋
有些题目的可选状态有以下特征
-
需要寻找最值
-
可选状态区间平移
-
存在可以永久去除的多余状态
感性的讲，可行性是一个滑动窗口，状态两两之间都可以 ⌈ 直接比较出优劣 ⌋ 且 ⌈ 优劣比较可以传递 ⌋
这样就有可能可以单调队列优化力
对于两个状态 \(i,j\) ，如果 \(j\) 比 \(i\) 贡献好，失效晚，那么这个 \(i\) 就没有任何价值，非常的逊，否则 \(i,j\) 都是有可能成为队首滴，一个可以 ⌈ 用实力碾压对手 ⌋ ，一个可以 ⌈ 等对手退役 ⌋
我们维护一个单调的队列，使得队列越前面的选择越优秀，保持队列单调
每次我们做出以下行动
-
去除队首多余状态
-
去除队尾比新状态逊的状态
-
队首即为所求，取用
-
加入新状态
这里要注意的是这些步骤顺序要 ⌈ 结合题目具体考虑 ⌋ 哦 QWQ
斜率优化
tmd 的有点折磨人
我们要考虑 \(j_1,j_2(j_2>j_1)\) 两个决策之间的优劣
先写出 \(j_x->i\) 的贡献，注意如果这里有平方之类的东西我们需要强拆化简掉
之后考虑何时 \(j_2\) 比 \(j_1\) 优，注意参数分离哦
化式子的时候我们要着力于将只含 \(j_1,j_2\) 或者含有 \(j1,j2\) 的三种尽力分来来，为了让状态相对独立 ，然后含有 \(j_x\) 的式子可能有点长，我们用函数代替掉
最后，写成斜率式子，形式类似 \(t(j_1,j_2)=\frac{y(j_1)-y(j_2)}{x(j_1)-x(j_2)}<g(i)\) 啦！
这种左边 ⌈ 两点成斜率 ⌋ 的式子可以使用一种大法： ⌈ 斜率优化 ⌋
注意这里的函数 \(x(i),g(i)\) 要单调哦
我们用 \(j_1,j_2,...,j_k\) 表示队列中的决策哈
那么有两个重要的结论
- \(t(j_r,j_{r+1})<g(i)\) 之类的，反正满足那个式子，且最优决策在队首队尾之类的地方，看题目的单调性具体咋样
大概这样
- 可以维护相邻决策之间的斜率单调减或者增
大概这样
总结一下，大概这样
另外还有一种理解方式，\(g(i)\) 左右对应两种不同答案，一边一种优
和这样
(图片转自 WC2016 课件)
另外，如果 \(g(i)\) 不单调了，可以不弹队列一端，然后二分