ConanKIDの小窝

ConanKIDの小窝

斜率优化DP学习笔记

posted on 2021-08-16 21:46:04 | under 学习笔记 |

我是个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;
}

几道练习题:


没了