xielv 1

简介

线性DP中有两类DP状态转移方程式：

1.状态转移中每一项中仅含阶段变量i或状态变量j（1D/1D）

2.状态转移中每一项中同时含阶段变量i与状态变量j

如果使用暴力DP的话毫无疑问两种都是O(n^2),此时面对n=1e5无能为力

但是，回归循环代码，我们会发现有些转移是没有必要的

砍掉这些没有必要的转移，能够有效地解决时间问题（类比最优性剪枝）

如果我们砍掉了没有必要的转移，就相当于维护决策单调性（最优往往对应单调）

单调队列

针对1D/1D状态转移方程，如果把外层循环的阶段变量i定住，会发生什么？

这时，有f[i]仅与变量j有关，那么这个时候就可以把所有与j有关的变量看成整体

我们只关注最优的决策，所以维护一个能够支持查询最优的数据结构

单调队列就是主场：

O(1)维护最值，显然快于其他数据结构，同时代码1行STL解决

我们只需要在队头排除不合法情况再在队尾插入较优决策即可

由于单调性，队头显然（并且应当）是最优决策

对于每个阶段i，取队首决策状态转移，然后将这一变量作状态插入候选队列即可

它的核心思想，维护决策单调性

斜率优化

针对同时含i和j的式子，这时显然单调队列不管用了，那么如何解决？

先将式子变一下形，变成一个正常的式子

把式子推成直线式

方便维护，那就j是自变量，只含j的项是因变量，同时含i，j的项中i是斜率，只有i的式子就是定值b

那么我们要做的，就是b最优

假设有一个决策k比决策j优，我们肯定能推出来决策k比决策j优的等价不等式

然后依据这个式子去判断维护什么样的决策点

对于最后的最优决策点，直接上状态转移方程

然后是维护上下凸壳的问题，这个时候前边提到的b最优就可以启示我们维护什么样的式子

数形结合即可解决战斗