斜率优化DP

介绍

斜率DP一般用于解决类似于如下的问题：

$$dp[i] = \min\limits_{j<i} \{ g(j) + f(i, j) + h(i)\}$$

• 注意到上述式子中，当我们固定 $i$，仅有的变量为 $j$，需要最小化的是 $g(j) + f(i, j)$。

我们看一个例子（例1）：

$$dp[i] - (s_i - L’)^2 = \min\limits_{j < i} \{dp[j] + s_j^2 + 2s_j(L’ - s_i)\}$$

在这个式子中，$L'$ 是一个定值，$s_i$ 代表 $sum[i] + i$，所以对于固定的 $i$，$(s_i - L’)^2$ 也是一个定值，所以变量也就只有 $j$，如何快速找到这样的 $j$ 是斜率优化DP要解决的问题。

对于这一类问题，我们列出式子 $y=kx+b$，也就是 $b=y-kx$。

一般来说，变量的意义如下：

$b$：需要最大化/最小化的项，一般形式为 $dp[i] + h(i)$

$y$：仅包含 $j$ 的项，一般形式为 $g(j)$

$kx$：包含 $i,j$ 的项，一般形式为 $f(i,j)$，其中 $x$ 需要单调递增 (如果不是，需要两边同乘 $-1$)，并且一般 $x$ 是 $f(i,j)$ 中代表 $j$ 的部分，$k$ 是 $f(i,j)$ 中代表 $i$ 的部分。

假设我们要最小化 $b$ 的值，那么需要直线 $y=kx+b$ 的截距最小。

那么根据上述式子，我们令

$$b_i = dp[i] - (s_i - L’)^2$$

$$y_j = dp[j] + s_j^2$$

$$k_i=-2(L’-s_i)$$

$$x_j = s_j$$

转移方程就有

$$b_i=\min\limits_{j<i} \{ y_j - k_ix_j \}$$

如果我们把 $(x_j,y_j)$ 看作二维平面上的点，则 $k_i$ 就是斜率，$b_i$ 代表一条过 $(x_j,y_j)$ 的斜率为 $k_i$ 的直线的截距，那么问题转化为选择合适的点 $j$，最小化截距。

我们发现，在求 最小值 的情况下，只有那些在这个点集中的 下凸包 上的点，才有可能作为最优的 $j$。

具体是哪个点呢？

我们发现，如果将直线 $y=kx+b$ 从下往上移动，第一个碰到的点 $j$ 就是最优决策点。

从图中可以发现，这个最优决策点 $j$ 一定满足条件：它是最小的 $j$，使得直线 $(j,j+1)$ 的斜率 $>k$。

由于下凸包中，$\forall i < j$，直线 $(i, i+1)$ 的斜率一定小于直线 $(j,j+1)$ 的斜率，所以这样的 $j$ 可以用二分找到。

不过这道题更简单，因为 $k_i$ 随着 $i$ 的增加而单调递减，所以用单调队列维护凸包即可。

最后看下如何用单调队列维护一个点集的下凸包：

只要在插入一个新的点 $i$ 时，判断是否满足以下条件：

插入前，队列里至少有两个元素
$k(q_{r-1}, q_r) > k(q_r, i)$

那么就一直pop队尾，直到上述两个条件之一不满足即可。

所以在这个单调队列的头部所储存的 $j$ 就是对于这个 $i$ 的最佳转移点。

例题

例1 [HNOI2008]玩具装箱

题意

给定一个正整数数组 $C_1, C_2, …, C_n$，我们将其分为若干个连续的段，如果 $C_i, … C_j$ 被放进了同一段中，那么这一段的长度被定义为 $x=j-i+\sum\limits_{k=i}^j C_k$。

给定一个常数 $L$，每一段的费用为 $(x-L)^2$，求一个最优分段方式，使得费用最小。

其中，$n \leq 5 \times 10^4, 1 \leq L \leq 10^7, 1 \leq C_i \leq 10^7$。

题解

设 $dp[i]$ 为前 $i$ 个元素的最小费用，那么

$$dp[i] = \min\limits_{j \leq i} \{dp[j] + (i-j+\sum\limits_{k=j}^i C_k-L)^2\}$$

调整为 $j < i$ 有

$$dp[i] = \min\limits_{j < i} \{dp[j] + (i-j+1+\sum\limits_{k=j}^i C_k-L)^2\}$$

那么设 $s_i = p_i + i$，其中 $p_i$ 为前缀和，$p_i = \sum\limits_{j=1}^i C_j$，令 $L’ = L+1$，

化简后可得

$$dp[i] - (s_i - L’)^2 = \min\limits_{j < i} \{dp[j] + s_j^2 + 2s_j(L’ - s_i)\}$$

接下来解法与上面写的相同。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
ll dp[maxn];
int n; 
ll L;
ll a[maxn];
int q[maxn<<1], head = 0, tail = -1;
ll s[maxn];

inline ll X(int i) { return s[i]; }
inline ll Y(int i) { return s[i] * s[i] + dp[i]; }
inline double slope(int i, int j) {
    return (long double)(Y(j) - Y(i)) / (X(j) - X(i));
}

int main() {
    cin >> n >> L;
    for (int i = 1; i <= n; i++) cin >> a[i], s[i] = s[i-1] + a[i];
    for (int i = 1; i <= n; i++) s[i] += i;
    L++;

    q[++tail] = 0;
    for (int i = 1; i <= n; i++) {
        
        while (head < tail && slope(q[head], q[head+1]) < 2 * (s[i] - L)) head++;  // 寻找最佳决策点
        int j = q[head];  // 最优决策点

        dp[i] = dp[j] + (s[i] - L - s[j]) * (s[i] - L - s[j]);

        while (head < tail && slope(q[tail], i) < slope(q[tail-1], q[tail])) tail--;
        q[++tail] = i;
    }
    cout << dp[n] << "\n";
}

例2 CF1715E Long Way Home

题意

一个包含 $n$ 个点，$m$ 条边的无向图中，每条边有权值 $w_i$。同时我们拥有 $k$ 次使用传送门的机会，从点 $u$ 传送到点 $v$ 会花费 $(u-v)^2$ 的时间。

求对于所有的点 $i$，从 $1$ 出发，到达点 $i$ 所需要的最短时间。

其中，$n, m \leq 10^5, 1 \leq k \leq 20, 1 \leq w_i \leq 10^9$。

题解

看到 $k \leq 20$ 就想到了 DP或者分层图。

再看到 $(u-v)^2$ 这个奇怪的平方，就确定了是斜率 DP。

设 $dp(i, k)$ 代表已经传送了 $k$ 次，到了点 $i$ 所花费的时间。

那么

$$dp(i, k) = \min\limits_{j \in [1,n]} \{dp(j, k-1) + (i-j)^2\} = \min\limits_{j \in [1,n]} \{dp(j, k-1) + i^2 + 2ij + j^2\}$$

设 $b = dp(i,k) - i^2, x = j, k = 2i, y = dp(j, k-1) + j^2$。

接下来就是斜率DP的套路了。

本题需要特别注意几点：

在每次 DP 后，要再跑一次 dijkstra，因为使用一次传送门以后，可能会对最短路有影响（比如某个最短路中间穿插了几次传送），处理方式就是在 Dijkstra 一开始的时候就把所有的点的 dis 更新好，然后全部扔进 pq 里。
在斜率 DP 过程中，由于没有 $j<i$ 这个限制条件，所以不再是转移的过程中维护凸包，而是一开始就将凸包建好，然后直接转移。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5+5;
struct Edge {
    int to, nxt;
    ll w;
} edges[maxn<<1];
int head[maxn], ecnt = 1;
void addEdge(int u, int v, int w) {
    Edge e = {v, head[u], w};
    head[u] = ecnt;
    edges[ecnt++] = e;
}
ll dp[maxn][21];
 
ll dis[maxn];
struct Node {
    int u;
    ll d;
    bool operator<(const Node& other) const {
        if (d == other.d) return u < other.u;
        return d > other.d;  // 大顶堆
    }
};
priority_queue<Node> pq;
bool vis[maxn];
int n, m;
void dijkstra(int k) {
    memset(vis, 0, sizeof(vis));
    memset(dis, 63, sizeof(dis));
    for (int i = 1; i <= n; i++) {
        dis[i] = dp[i][k];
    }
    while (pq.size()) pq.pop();
 
    dis[1] = 0;
    for (int i = 1; i <= n; i++) {
        pq.push({i, dis[i]});  // 开始先将所有的点扔进去
    }
    // pq.push({1, 0});
    while (pq.size()) {
        Node nd = pq.top(); pq.pop();
        int u = nd.u;
        if (vis[u]) continue;
        vis[u] = 1;
        ll d = nd.d;
        for (int e = head[u]; e; e = edges[e].nxt) {
            int v = edges[e].to;
            ll w = edges[e].w;
            if (d + w < dis[v]) {
                dis[v] = d + w;
                pq.push({v, dis[v]});
            }
        }
    }
    for (int i = 1; i <= n; i++) dp[i][k] = min(dp[i][k], dis[i]);
}
 
inline ll X(ll i, int k) { return i; }
inline ll Y(ll i, int k) { return dp[i][k-1] + i*i; }
inline long double slope(int i, int j, int k) {
    return ((long double)(Y(j,k) - Y(i,k)) / (X(j,k) - X(i,k)));
}
int q[maxn<<1], hd = 0, tail = -1;
void DP(int k) {
    hd = 0, tail = -1;
    // 需要先加所有的转移点，因为 j<i 的限制不成立！
    for (ll i = 1; i <= n; i++) {
        while (hd < tail && slope(q[tail-1], q[tail], k) > slope(q[tail], i, k)) tail--;
        q[++tail] = i;
    }
 
    for (ll i = 1; i <= n; i++) {
        while (hd < tail && slope(q[hd], q[hd+1], k) <= 2*i) hd++;
        ll j = q[hd];  // 最佳决策点
        dp[i][k] = min(dp[i][k], i*i + dp[j][k-1] + j*j - 2*i*j);
    }
}
 
 
int k;
int main() {
    cin >> n >> m >> k;
    memset(dp, 63, sizeof(dp));
    for (int i = 1; i <= m; i++) {
        int u, v, w; cin >> u >> v >> w;
        addEdge(u, v, w); addEdge(v, u, w);
    }
    dijkstra(0);
    for (int K = 1; K <= k; K++) {
        DP(K);
        dijkstra(K);
    }
    for (int i = 1; i <= n; i++) {
        ll ans = 1e18;
        for (int j = 0; j <= k; j++) ans = min(ans, dp[i][j]);
        cout << ans << " ";
    }
    cout << endl;
}

Contents

介绍

例题

例1 [HNOI2008]玩具装箱

例2 CF1715E Long Way Home