dp 的优化

单调队列优化

对于转移方程

$f_x=\min _{k=p_x}^{x-1}\{g_k\}+w_x$fx​=k=px​minx−1​{gk​}+wx​

其中 $p_x$px​ 单调不降。如果存在两个数 $j,k$j,k 有 $j \leq k$j≤k 且 $g_k \leq g_j$gk​≤gj​，那么决策 $j$j 是无用的。这意味着我们的最优决策表单调不降，所以可以用一个单调递增的队列进行优化。流程如下

1. 队首元素不断出队，直到队首元素在给定范围中，此时队首元素就是状态 $f_x$fx​ 的最优决策。
2. 计算 $g_x$gx​，并插入单调队列的尾部，同时维护队列单调递增性。
3. 重复上述步骤，可以发现每个状态只入队和出队一次，时间复杂度为 $O(n)$O(n)。

斜率优化

直接讲比较迷，拿 HNOI2008 玩具装箱为栗子。

设 $f_i$fi​ 是装好前 $i$i 个玩具的花费，枚举从那个玩具开始放。$O(n^2)$O(n2) 的转移方程如下

令 $s_i = \sum_{k=1}^i c_k$si​=∑k=1i​ck​ 有

$f_i = \min_{j=0}^{i - 1} f_j+(s_i-s_j + i - j - 1 - L)^2$fi​=j=0mini−1​fj​+(si​−sj​+i−j−1−L)2

再令 $s_i = \sum_{k=1}^i c_k+i$si​=∑k=1i​ck​+i，$L = L+1$L=L+1 有

$f_i = \min_{j=0}^{i - 1} f_j+(s_i-s_j -L)^2 \\ \text{化简得}\\ f_i=s_i^2-2s_i \times L+f_j+(s_j+L)^2-2s_is_j \\ \text{移同类项得}\\ f_j+(s_j+L)^2 =2s_is_j+ f_i - s_i^2 + 2s_i \times L\\$fi​=j=0mini−1​fj​+(si​−sj​−L)2化简得fi​=si2​−2si​×L+fj​+(sj​+L)2−2si​sj​移同类项得fj​+(sj​+L)2=2si​sj​+fi​−si2​+2si​×L

令 $y = f_j+(s_j+L)^2$y=fj​+(sj​+L)2、$k = 2s_i$k=2si​、$x =s_j$x=sj​、$b = f_i - s_i^2 + 2s_i \times L$b=fi​−si2​+2si​×L。那么得到了

$y = kx + b$y=kx+b

其中 $x$x 满足单调递增性，所以不用对柿子取反。同时，$k$k 和关于 $j$j 的解析式 $y$y 也单调递增，而 $b$b 中有要转移的 $f_i = b + s_i^2 - 2s_i \times L$fi​=b+si2​−2si​×L。

可以发现斜率 $k$k 数已知的，并且 $b - f_i$b−fi​ 也是已知队。如果能求出一个点对 $(x,y)$(x,y)，就可以求出 $b$b，进而求出 $f_i$fi​。要让 $f_i$fi​ 最小就要让 $b$b 最小，如果把 $(x,y)$(x,y) 展现在坐标系上，我们用一条斜率为 $k$k 的直线从右下方向左上方移动，第一个在直线上的 $(x,y)$(x,y) 即为需要的点。

考虑加一个点得到了直线 $k_2$k2​，之前可选的点集中有一条直线 $k_1$k1​。如果 $k_2 > k_1$k2​>k1​，那么加的点在以后可能用到，因为随着斜率的单调递增，选的点也逐渐靠上。如果 $k_1 < k_2$k1​<k2​，那么 $k_1$k1​ 能交的线，$k_2$k2​ 一定比它先交，所以 $k_1$k1​ 可以从点集中删除。

所以要维护的点集是一个下凸包。下凸包所有点的斜率是单调递增的，而且下凸包的下方没有其它的点。用单调队列维护，实现有亿点点细节。

四边形不等式优化