用单调队列优化动态规划

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

整个单调队列优化会为后面的斜率优化做基础（因为我学这个单调队列优化就是有一道题要求使用斜率优化），所以请务必搞懂这个操作。