斜率优化 DP - 洛谷保存站

# 前言
###### ~~（为什么现在才来写斜率优化的总结我也不知道）~~  
斜率优化 DP 是动态规划中十分重要的一类优化方法，难度约为省选，洛谷上的很多板子题也都是紫的。但其难度并不算大，模板都一样，只需要会根据题目的条件推一些简单式子，那么基础的斜率优化DP就掌握得差不多了。~~（至于进阶的，显然我是个蒟蒻根本不会）~~

# 引入
对于状态转移方程 $f_i=\min(w_i+w_j+f_j)$，我们可以通过**单调队列优化**使它的复杂度达到线性；但是很多时候，转移时并不是一个一次式，比如说 $f_i=\min(w_i^2-w_iw_j+w_j^2+w_i+w_j+f_j)$，那么单调队列优化在此时就显得不适用了。像上面那样出现了交叉项的情况，我们就可以使用**斜率优化**使得复杂度达到线性。

# 主要思想
以上面的那个转移式为例，我们设当上式中的 $j\gets k$ 时 $f_i$ 取到最小值，那么有
$$f_i=w_i^2-w_iw_k+w_k^2+w_i+w_k+f_k$$
$$w_k^2+w_k+f_k=w_iw_k+f_i-w_i^2-w_i$$
令 $y=w_k^2+w_k+f_k,\ x=w_k,\ k=w_i,\ b=f_i-w_i^2-w_i$，则上式等同于
$$y=kx+b$$
其中的 $x$、$y$ 与 $i$ 无关，$k$、$b$ 只与 $i$ 有关,而我们最终的目的是使得 $b$ 尽可能小。注意到，这是一个标准的**直线方程**，而我们要求的其实就是**截距**。所以，我们一起考虑**数形结合**，从图形的角度思考问题。首先，我们根据求出的 $1\sim i-1$ 的数据，我们可以在平面直角坐标系中找到这些点，如图：

![斜率优化1.PNG](https://cdn.acwing.com/media/article/image/2023/06/06/104910_32ce9c5a04-斜率优化1.PNG)

这些点对应的截距为：

![斜率优化2.PNG](https://cdn.acwing.com/media/article/image/2023/06/06/104910_5c21ffda04-斜率优化2.PNG)

不难发现，真正对答案有贡献的只有那些**下凸包**的点（若是取 $\max$ 则改为**上凸包**），即：

![斜率优化3.PNG](https://cdn.acwing.com/media/article/image/2023/06/06/104910_72a398ea04-斜率优化3.PNG)

而那些其余的点，一定不会比这些点更优。所以我们只需维护一个下凸包即可。至于维护方式，仍是我们喜闻乐见的**单调队列**。这样，就可以把本来 $O(n^2)$ 的时间复杂度降至 $O(n)$。

## 例题
[P3195 [HNOI2008]玩具装箱](https://www.luogu.com.cn/problem/P3195)

对于所有的斜率优化题，首先必须要先写出式子。设 $c$ 的前缀和数组为 $s$，那么不难得到 DP 方程（见代码），并将其化为上面的那种形式。  
接下来就是用单调队列维护凸包的过程。
```
/*
f[i] = min{f[j] + (s[i] - s[j] + i - j - 1 - l) ^ 2}
令s[i] + i = a[i], s[i] + i + l + 1 = b[i]
f[i] = f[j] + (a[i] - b[j]) ^ 2
f[j] + b[j] ^ 2 = 2 * a[i] * b[j] + f[i] - a[i] ^ 2
*/
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;

const int N = 5e4 + 10;
int n, l;
LL a[N], b[N], c[N];
LL f[N];
int q[N], hh = 1, tt;

LL Y(int x)
{
	return f[x] + b[x] * b[x];
}

int main()
{
	cin >> n >> l;
	for(int i = 1; i <= n; i++)
	{
		scanf("%lld", &c[i]);
		c[i] += c[i - 1];
	}
	for(int i = 0; i <= n; i++)
		a[i] = c[i] + i, b[i] = c[i] + i + l + 1;
	
	memset(f, 0x3f, sizeof(f));
	f[0] = 0;
	q[++tt] = 0;
	for(int i = 1; i <= n; i++)
	{
		while(hh < tt && Y(q[hh + 1]) - Y(q[hh]) <= 2 * a[i] * (b[q[hh + 1]] - b[q[hh]]))
			hh++;
		int j = q[hh];
		f[i] = f[j] + (a[i] - b[j]) * (a[i] - b[j]);
		while(hh < tt && (Y(i) - Y(q[tt])) * (b[q[tt]] - b[q[tt - 1]]) <= (Y(q[tt]) - Y(q[tt - 1])) * (b[i] - b[q[tt]]))
			tt--;
		q[++tt] = i;
	}
	
	cout << f[n] << endl;
	return 0;
}
```

代码中维护凸包的过程中用到了**斜率**，但为了避免浮点数带来的误差，尽量使用乘法的方式进行比较。（事实上，也有很多人仍在使用浮点数的写法。那种方法更容易理解，也更不容易出错（比如爆 int 之类的）。初学者可以那样写，但是还是建议用整数类型进行运算）

# 总结
对于斜率优化的题目，我个人的习惯是在代码前面把式子变形的过程写下来，方便后面的差错或者是复习。  
另外，从上面的代码也看得出来，这里的变量实际上是需要满足一些条件的：

- （$\min$，下凸包）若 $i<j$，则 $k_i<k_j$
- （$\max$，上凸包）若 $i<j$，则 $k_i>k_j$
- $f_i$ 前的系数应为正数

前两点是为了满足在单调队列中，若某个前缀在当前状态下不是最优的，则它们对于之后状态的贡献也一定不是最优的。只有这样，才可以通过弹出队首的方式使得复杂度达到线性。第三点是最基础的，因为只有这样才能保证 $b_{\min}\to f_{\min},b_{\max}\to f_{\max}$。

## 模板
```
#include<bits/stdc++.h>
using namespace std;
#define Y(x) ()

const int N = ;
int n, w[N], f[N];
int q[N], hh = 1, tt;

int main()
{
	scanf("%d", &n);
	for(int i = 1; i <= n; i++)
		scanf("%d", &w[i]);
	
	q[++tt] = 0;
	for(int i = 1; i <= n; i++)
	{
		while(hh < tt && Y(q[hh + 1]) - Y(q[hh]) <= k * (X(q[hh + 1]) - X(q[hh]))) hh++;
		int j = q[hh];
		f[i] = ;
		while(hh < tt && (Y(i) - Y(q[tt])) * (X(q[tt]) - X(q[tt - 1])) <= (Y(q[tt]) - Y(q[tt - 1])) * (X(i) - X(q[tt]))) tt--;
        q[++tt] = i;
	}
	
	printf("%d\n", f[n]);
	return 0;
}
```

# 应用
[斜率优化专项练习题单](https://www.luogu.com.cn/training/5352#problems)

这里选 $2$ 道我本人认为有意义的题目来谈一谈：

[P2365 任务安排](https://www.luogu.com.cn/problem/P2365)

此题数据非常小，当然可以用普通的暴力 DP 过掉。不过我们应该要以精益求精的精神，尝试一下此题的线性写法。  
[AcWing301 任务安排2](https://www.acwing.com/problem/content/303/)   
（~~好吧其实是被迫的~~）  
这个题相较于其他题多了一个转化的步骤，需要**费用提前计算**。除去这一步，这个题就变成一道纯纯正正的板题了。

[P5785 [SDOI2012]任务安排](https://www.luogu.com.cn/problem/P5785)

这个题坑人的点是斜率，它并不是单调递增的，不满足上面写的斜率优化的条件，所以不能像平常一样处理。正解是全程不弹出队首，每次用二分的方式找到那个转移点，时间复杂度是 $O(n\log n)$ 的。

# 补充
从上文可以发现，**斜率** $k$ 和**横坐标** $x$ 必须要满足一定的单调性。（斜率与 $\min\max$ 相关，$x$ 则要求单调递增）

- 斜率没有单调性时，**凸包上二分**。
- 横坐标没有单调性时，用**李超线段树/CDQ 分治/平衡树**来维护凸包。

# 结语
斜率优化 DP 是一个需要稍加练习的算法，初学者可能理解起来有点抽象，但是自己实操几个题就可以基本理解斜率优化的主要思想了。

upd20230719：对于那些超出了范围限制的题目，即不满足单调性的情况下，可以使用**李超线段树**解决。

upd20230829：加入了对于非单调时的进一步讨论。

正在渲染内容...