斜率优化DP学习笔记

· · 个人记录

我是个DP菜鸡实锤了

先来看题

考虑DP，应该很容易可以得出状态转移方程。设 dp_i 表示前 i 个单词进行分组的代价，显然

dp_i=\min\limits_{0\le j<i }\{dp_j+(sum_i-sum_j)^2+m\}

其中 sum 表示前缀和。

但是朴素计算这个东西的复杂度是 O(n^2) 的，我们无法承受。因此必须优化。枚举 dp_{1-n} 的循环显然是不可少的，因此只能在计算状态转移方程上做文章。

若 j<k，考虑决策 k 比决策 j 更优的条件：

dp_j+(sum_i-sum_j)^2+m\ge dp_k+(sum_i-sum_k)^2+m

将其拆开

dp_j+sum^2_i+sum^2_j-2sum_isum_j+m\ge dp_k+sum^2_i+sum^2_k-2sum_isum_k+m dp_j+sum^2_j-2sum_isum_j\ge dp_k+sum^2_k-2sum_isum_k

将含 sum_i 的项移到一边去

2sum_i(sum_k-sum_j)\ge dp_k+sum^2_k-dp_j-sum^2_j 2sum_i\ge\dfrac{dp_k+sum^2_k-dp_j-sum^2_j}{sum_k-sum_j}

这个式子的右边就长得很像斜率了。

而我们发现 sum_i 是单调递增的。也就是说，如果对于状态 i，决策 k 优于 j，那么随着 sum_i 的增大，上述式子一定始终成立。这样的话，我们在之后的计算过程中，就完全可以不考虑 j 这个“废点”。

因此，我们可以维护一个单调队列，保存所有合法的决策点。在整个过程中，一旦遇到队头两点 j,k 组成的“斜率”——也就是上面式子的右边——小于等于 2sum_i，就可以直接把点j从队列里给pop掉（因为它将永远不会优于点 k）。同时，我们每枚举到一个状态 i，就要将点 i 入队，同时维护队内相邻两点的斜率的单调性（这也是为了及时排除无用决策，原理同上）。

这样一来，每个点至多入队和出队一次，我们就做到了 O(n) 的复杂度。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m;
int a[500005];
int sum[500005], dp[500005];
int q[500005];
int up(int x, int y) {return dp[y] + sum[y] * sum[y] - dp[x] - sum[x] * sum[x];}//点x和点y组成的斜率的分子
int down(int x, int y) {return sum[y] - sum[x];}//同上，分母
void work() {
    memset(dp, 0, sizeof(dp)); memset(q, 0, sizeof(q)); memset(sum, 0, sizeof(sum));
    for (int i = 1; i <= n; i++)
        cin >> a[i], sum[i] = sum[i - 1] + a[i];
    int l = 1, r = 1; q[1] = 0;
    for (int i = 1; i <= n; i++) {
        while(l + 1 <= r && up(q[l], q[l + 1]) <= 2 * sum[i] * down(q[l], q[l + 1])) l++;//一旦发现推的式子成立，就排除队头决策
        int j = q[l];
        dp[i] = dp[j] + (sum[i] - sum[j]) * (sum[i] - sum[j]) + m;//这时可以直接取出队头计算了，由于队内斜率的单调性，q[l]一定最优
        while (l + 1 <= r && up(q[r - 1], q[r]) * down(q[r], i) >= up(q[r], i) * down(q[r - 1], q[r])) r--;//维护决策单调性
        q[++r] = i;//把i入队
    }
    cout << dp[n] << endl;
}
signed main() {
    while (cin >> n >> m)
        work();
    return 0;
}

把分子和分母单独写一个函数应该会比较清楚吧。

再来看这个

考虑朴素DP：

dp_i=\min\limits_{0\le j<i}\{dp_j+(sum_i-sum_j+i-j-1-L)^2\}

发现这个式子比较臃肿，可以换个元。设 h_i=sum_i+i，g_i=sum_i+i-1-L。于是可以改写为

dp_i=\min\limits_{0\le j<i}\{dp_j+(g_i-h_j)^2\}

接下来就是一样的套路。考虑若 j<k，决策 k 优于 j 的条件：

dp_j+(g_i-h_j)^2\ge dp_k+(g_i-h_k)^2 dp_j+h^2_j-2g_ih_j\ge dp_k+h^2_k-2g_ih_k 2g_i(h_k-h_j)\ge dp_k+h^2_k-dp_j-h^2_j 2g_i\ge \dfrac{dp_k+h^2_k-dp_j-h^2_j}{h_k-h_j}

由于 g_i 也是单调递增的，所以也可以维护一个斜率递增的单调队列，然后及时排除无用决策。复杂度 O(n)。这题代码和上面几乎一模一样，就不给了。

Q：何时可以考虑斜率优化DP？

A：状态转移方程遵循如下形式：

dp_i=\min\{dp_j+val(i,j)\}

其中 val 是一个与 i,j 均有关的多项式（一般和前缀和有关，这样才能利用单调性进行决策点的维护）。这个时候就可以推一推式子，再利用决策单调性进行优化了。

一道经典题

这道题挺有意思的，做法很多。设第 i 个人坐上车的时间为 time_i，那么答案就是 \sum(time_i-t_i)，即 \sum time_i-\sum t_i。发现后面那个 \sum t_i 是固定的，所以只需要让前面的部分最小即可。

设 dp_i 表示接送完前i分钟的所有学生所需的最小代价，易得状态转移方程：

dp_i=\min\limits_{0\le j\le i-m}\{dp_j+i(sum_i-sum_j)\}

其中 sum_i 表示前 i 分钟来等车的总人数。

我们发现 i(sum_i-sum_j) 是一个与 i,j 均有关的多项式，因此显然是可以推一推式子然后斜率优化的。式子这里就不推了，很套路。

代码稍有不同。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n, m, maxt;
int a[505];
int sum[4000005];
int dp[4000005];
int q[4000005];
int ans = 1e18;
int up(int x, int y) {return dp[y] - dp[x];}
int down(int x, int y) {return sum[y] - sum[x];}
signed main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        sum[++a[i]]++; maxt = max(maxt, a[i]);
    }
    for (int i = 1; i <= maxt + m; i++)
        sum[i] += sum[i - 1];
    int l = 1, r = 1; q[1] = 0;
    for (int i = 1; i <= maxt + m; i++) {
        if (i > m) {
            int x = i - m;
            while (l + 1 <= r && up(q[r - 1], q[r]) * down(q[r], x) >= up(q[r], x) * down(q[r - 1], q[r])) r--;
            q[++r] = x;
        }//由于此时i-m也是决策的一个候选项，所以先将i-m入队
        while (l + 1 <= r && up(q[l], q[l + 1]) <= i * down(q[l],q[l + 1])) l++;
        int j = q[l];
        dp[i] = dp[j] + (sum[i] - sum[j]) * i;
        if (i >= maxt) ans = min(ans, dp[i]);//注意答案要取最小值
    }
    for (int i = 1; i <= n; i++)
        ans -= a[i];
    cout << ans << endl;
    return 0;
}

几道练习题：

没了