Introduction
有的时候我们在日常写题时，会碰见这样的毒瘤 DP 题目，他们一般有以下特性：
- 多维度动态规划
- 循环层数很多，在极限数据下无法 AC。
- 一般出现在区间 DP 中，一般暴力算法复杂度为\(O(n^3)\)。
这个时候我们可以使用单调队列来优化，时间复杂度可以进一步降至\(O(n^2)\)或者是\(O(nm)\)。如果有不会单调队列的同学呢可以去学习以下，顺便可以看看这篇文章：CH1201:最大子序和题解
Overall on this optimization technique
我们来看一道例题：Fence – POJ这道题是一道比较简单的经典 DP。设计状态\(dp[i][j]\)表示前\(i\)个人搞定了前\(j\)个单位的墙。写出方程式：
\[dp[i][j] = min_{S_i – l_i \leq k < S_i}\{dp[i-1][k]+profit_i*(j-k)\}\]
这样的话，整个算法的复杂度是\(O(n^3)\)的。我们能不能将其降为\(O(n^2)\)呢？我们可以把整个方程变个形，之后方程是这样的：
\[dp[i][j] = min_{S_i – l_i \leq k < S_i}\{dp[i-1][k]-profit_i*k\}+profit_i*j\]
我们发现，这样的话整个方程在\(i\)的循环之下，算是只跟变量\(k\)扯上关系了。我们会发现，只要有\(k_1<k_2\)且\(dp[i-1][k_1]-profit_i*k_1<dp[i-1][k_2]-profit_i*k_2\)，那么就可以直接排除掉答案\(k_1\)。那么就可以使用单调队列来做到这一点。
下面是核心的 DP 代码：
int calc(int i, int k)
{
return dp[i - 1][k] - wks[i].p * k;
}
// in ( int main() )
for (int i = 1; i <= k; i++)
{
deque<int> q;
for (int j = max(0, wks[i].s - wks[i].l); j <= wks[i].s - 1; j++)
{
while (!q.empty() && calc(i, q.back()) <= calc(i, j))
q.pop_back();
q.push_back(j);
}
for (int j = 1; j <= n; j++)
{
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if (j >= wks[i].s)
{
while (!q.empty() && q.front() < j - wks[i].l)
q.pop_front();
if (!q.empty())
dp[i][j] = max(dp[i][j], calc(i, q.front()) + wks[i].p * j);
}
}
}
In Conclusion
整个单调队列优化会为后面的斜率优化做基础（因为我学这个单调队列优化就是有一道题要求使用斜率优化），所以请务必搞懂这个操作。
