经过了前几期的介绍，相信大家对主要的DP类型都有了一定的了解。但是你是否感受过好不容易想出了动规方程，但是却因时间复杂度过高而无法A题的烦恼呢？
今天，我来介绍一种动态规划的优化方法——斜率优化。
例题
（例题来源洛谷，侵删）
一个想法看到这道题，我们很容易就能想到一个O(N^2)的算法。
我们定义F[i]表示完成前i件物品的最少花费，转移方程显然：
动规方程
由于我们没有记录一共分了几段，所以对机器启动时间所造成的花费比较难以计算。这里，我们把费用提前，就是在i位置启动一次机器，i~n所有物品的完成时刻都要推迟s。所以，直接把这些花费加上去就行了。
这个算法的时间复杂度是O(N^2)的，可以通过这道题目。但是，如果N在大一点，到1e5，甚至1e6，该怎么办呢？
一个优化
这时候，就需要我们的斜率优化登场啦。
斜率优化讲解
Code
#include <bits/stdc++.h>
using namespace std;
const int N = 5005;
int f[N], t[N], sf[N], st[N];
int n, s, F[N], que[N], l, r;
double calc(int i, int j) {
return (F[i] - F[j]) / (sf[i] - sf[j]);
}
int main () {
scanf ("%d%d", &n, &s);
for (int i = 1; i <= n; ++i) {
scanf ("%d%d", &t[i], &f[i]);
sf[i] = sf[i - 1] + f[i];
st[i] = st[i - 1] + t[i];
}
que[l = r = 1] = 0;
for (int i = 1; i <= n; ++i) {
while (l < r && calc(que[l], que[l + 1]) < st[i] + s) l++;
F[i] = F[que[l]] + s * (sf[n] - sf[que[l]]) + st[i] * (sf[i] - sf[que[l]]);
while (l < r && calc(que[r - 1], que[r]) > calc(que[r], i)) r--;
que[++r] = i;
}
printf ("%d\n", F[n]);
return 0;
}
总结
斜率优化DP，有一个很明显的特征：每一个决策点可以用一个坐标来表示，决策之间的关系和坐标之间的斜率有关。通过单调队列，我们可以把DP的时间复杂度降一个维度，大大提高算法的效率。
【信息学竞赛从入门到巅峰】，一个专注于分享OI/ACM常用算法及知识的公众号。
