【总结】DP的常用优化

标签：总结 cdot 斜率 单调 cases 优化 DP

1.单调队列优化

2.斜率优化

2.1. 算法介绍

如果一类 \(dp\) 可以写为 \(f_i=\max/\min{a_i \cdot b_j + c_j + d_i}\)，即只和 \(i\)，\(j\) 有关的项和 一个 和 \(i\)，\(j\) 都有关的项的和，那么一般就可以使用斜率优化。

我们假设 \(j\) 为 \(i\) 的最优决策点，则有 \(f_i=a_i \cdot b_j + c_j + d_i\)，进行移项，改写形如 \(y=kx+b\) 的形式，得到 \(c_j = -a_i \cdot b_j + f_i - d_i\)

\[\begin{cases} y_i=c_i\\ k_i=-a_i\\ x_i=b_i\\ b_i=f_i-d_i\\ \end{cases} \]

2.2 例题

3.决策单调性

4.线段树优化

标签：总结,cdot,斜率,单调,cases,优化,DP
From： https://www.cnblogs.com/zhouziyi/p/16749283.html