浅谈 DP 优化 1

· · 算法·理论

虽然但是好像并不浅

由于本人是小升区 xxs，DP 学的不多，大部分内容都是边学边写，文章有错误还请多多谅解。

本篇文章学习了以下文章：

1. 单调队列优化 \text{DP}

1.1 一般形式

前置知识：单调队列。

单调队列往往可以优化形如以下的 DP：

dp_i = B_i + \max_{j = l_i}^{r_i} {dp_j + A_j}

其中 l_i, r_i 随 i 单调不减，A_x, B_x 只和 x 有关。

把 dp_j + A_j 放入优先队列然后取队头转移即可。

1.2 例题

1.2.1 \text{P1725}

模板题。

显然，转移方程为：

dp_i = a_i + \max_{j = i - r}^{i - l} dp_j

直接上单调队列优化即可。

:::success[code]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2e5 + 10;
int n, l, r;
int a[MAXN];
int dp[MAXN];
int que[MAXN];
int ans = LLONG_MIN;
signed main() {
    cin >> n >> l >> r;
    for (int i = 0; i <= n; i++) cin >> a[i];
    memset(dp, -0x3f, sizeof(dp));
    dp[0] = 0;
    int head = 1, tail = 1;
    for (int i = l; i <= n; i++) {
        while (head <= tail && dp[i - l] >= dp[que[tail]]) tail--;
        que[++tail] = i - l;
        while (que[head] + r < i)  head++;
        dp[i] = dp[que[head]] + a[i];
        if (i + r > n) ans = max(ans, dp[i]);
    }
    cout << ans;
    return 0;
}

:::

1.2.2 \text{P2569}

设 dp_{i, j} 表示当前是 i，持有 j 只股票赚到最多的钱。

考虑转移：

以第三种转移为例（第四种同理），将包含 j 的那一项提出来：

dp_{i, j} = \max(dp_{i, j}, \max_{k = j - as_i}^{j - 1} dp_{i - w - 1, k} - j\times ap_i + k\times ap_i)\\ dp_{i, j} = \max(dp_{i, j}, \max_{k = j - as_i}^{j - 1} dp_{i - w - 1, k} + k\times ap_i) - j\times ap_i

显然，可以单调队列优化。

:::success[code]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 2010;
int n, maxp, w;
int ap[MAXN], bp[MAXN], as[MAXN], bs[MAXN];
int dp[MAXN][MAXN];
int q[MAXN];
signed main() {
//  ios::sync_with_stdio(0);
//  cin.tie(0), cout.tie(0);
    cin >> n >> maxp >> w;
    for (int i = 1; i <= n; i++) cin >> ap[i] >> bp[i] >> as[i] >> bs[i];
    memset(dp, -0x3f, sizeof(dp));
    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= as[i]; j++) dp[i][j] = -1 * ap[i] * j;
        for (int j = 0; j <= maxp; j++) dp[i][j] = max(dp[i][j], dp[i - 1][j]);
        if (i <= w) continue;
        int head = 1, tail = 0;
        for (int j = 0; j <= maxp; j++) {
            while (head <= tail && q[head] < j - as[i]) head++;
            while (head <= tail && dp[i - w - 1][q[tail]] + q[tail] * ap[i] <= dp[i - w - 1][j] + j * ap[i]) tail--; 
            q[++tail] = j;
            if (head <= tail) dp[i][j] = max(dp[i][j], dp[i - w - 1][q[head]] - (j - q[head]) * ap[i]);
        }
        head = 1, tail = 0;
        for (int j = maxp; j >= 0; j--) {
            while (head <= tail && q[head] > j + bs[i]) head++;
            while (head <= tail && dp[i - w - 1][q[tail]] + q[tail] * bp[i] <= dp[i - w - 1][j] + j * bp[i]) tail--;
            q[++tail] = j;
            if (head <= tail) dp[i][j] = max(dp[i][j], dp[i - w - 1][q[head]] + (q[head] - j) * bp[i]);
        }
    }
    int ans = 0;
    for (int j = 0; j <= maxp; j++) ans = max(ans, dp[n][j]);
    cout << ans;
    return 0;
}

:::

1.3 习题

2. 斜率优化 \text{DP}

2.0 前置

对于一个斜截式 y = kx + b，其中 k 就是斜率，b 就是截距。

首先，我们考虑这样一个问题：平面上有 n 个点 (x_1, y_1), (x_2, y2), \dots, (x_n, y_n)，给出一个 k，对于点求过这个点且斜率为 k 的直线的截距为 y_i - kx_i，求截距的最大值和最小值。

我们假设有四个点 A, B, C, D，其中 D 在三角形 ABC 内部，则 D 不可能取到最值，因此不管 k 是何值，都可以通过上下移动过点 D 的斜率为 k 的直线。

证明略。

因此，将所有可能取到最值的点拿出来，会发现构成一个凸壳（一个包住所有点的凸多边形，凸多边形上不会有三点共线）。其中下凸壳可以取到最小值，并且下凸壳上从左往右相邻两点斜率递增；上凸壳可以取到最大值，并且上凸壳上从左往右相邻两点斜率递减。

2.1 基础部分

本节均以 \text{P3195} 为例。

2.1.1 方程改写

设 s_i = \sum_{j = 1}^i c_j，dp_i 表示将前 i 个玩具装入箱子的最小代价，则

dp_i = \min_{j = 0}^{i - 1} dp_j + (s_i - s_j + i - j - L - 1)^2

我们把 \min 去掉，并将 (s_i - s_j + i - j - L - 1)^2 打开，分成只和 i 有关，只和 j 有关，常量随便放。

dp_i = dp_j + (s_i + i)^2 + (s_j + j + L + 1)^2 - 2(s_i + i)(s_j + j + L + 1)

我们将转移中的项分为四项（形如 f(i)\times g(i) 的项称为交叉项）：

将转移方程写成 z = y - kx 的形式：

dp_i - (s_i + i)^2 = dp_j + (s_j + j + L + 1)^2 - 2(s_i + i)(s_j + j + L + 1)

2.1.2 数学推导

我们将 (x_j, y_j) = (s_j + j + L + 1, dp_j + (s_j + j + L + 1)^2) 当做平面上的一个点，k = 2(s_i + i) 当做斜率。

于是，我们需要最小化截距 z = dp_i - (s_i + i)^2。

那么，问题就变成了：平面上有 i - 1 个点 (x_1, y_1), (x_2, y_2), \dots, (x_{i - 1}, y_{i - 1})，已知斜率 k，求过这些点的斜率为 k 的直线的截距最小值。

根据之前的结论，截距会在下凸壳取到最小值。

考虑怎么求最小值。设点 (x, y) 在下凸壳左边的斜率为 k_1，右边斜率为 k_2，那么，当斜率为 k 的直线的 k_1\le k\le k_2 时，会在 (x, y) 取到最小截距。

由于斜率是单调递增的，如果当前 k_2 < k，显然这个点不可以取到最小值，于是将这个点删掉，也就是一路删点直到最左边两个点斜率 \ge k。

最后，考虑维护插入点 (x_i, y_i) 之后的下凸壳会怎么样。因为 x = 2(s_i + i + L + 1) 单调递增，而下凸壳斜率单调递增，所以 (x_i, y_i) 必然会出现在下凸壳上，插入后会导致下凸壳最后一段不满足单调递增的删除。

2.1.3 代码实现

我们使用单调队列维护下凸壳的所有点，每次计算 dp_i 时由于斜率单调递增而弹出队首，最后决策最优点会取到队首。加入完点 (x_i, y_i) 后弹出队尾若干点。

时间复杂度为 O(n)。

写代码时注意精度误差。

:::success[code]

#include <bits/stdc++.h>
#define int long long
#define ld long double
using namespace std;
const int MAXN = 5e4 + 10;
int n, L;
int head = 1, tail;
int q[MAXN], s[MAXN], dp[MAXN], a[MAXN];
//坐标和斜率 
int X(int i) { return s[i] + i + L + 1;}
int Y(int i) { return dp[i] + (s[i] + i + L + 1) * (s[i] + i + L + 1);}
ld slope(int i, int j) { return (ld)(Y(i) - Y(j)) / (ld)(X(i) - X(j));}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> L;
//  L++; 
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        s[i] = s[i - 1] + a[i];
    }
    head = tail = 1;
    for (int i = 1; i <= n; i++) {
        //弹出下凸壳斜率不超过 k 的点 
        while (head < tail && slope(q[head + 1], q[head]) <= 2 * (s[i] + i)) head++;
        dp[i] = Y(q[head]) - 2 * (s[i] + i) * X(q[head]) + (s[i] + i) * (s[i] + i);
        //弹出下凸壳不满足斜率单调递增的点
        while (head < tail && slope(i, q[tail]) <= slope(q[tail], q[tail - 1])) tail--;
        q[++tail] = i; 
    }
    cout << dp[n];
    return 0;
}

:::

2.2 例题

2.2.1 \text{P5784}

设 P_i = \sum_{j = 1}^i T_j, Q_i = \sum_{j = 1}^i C_j，dp_i 表示完成前 i 批任务所需的最小费用。

列出状态转移方程：

dp_i = \min_{j = 0}^{i - 1} dp_j + s(Q_n - Q_j) + P_i(Q_i - Q_j)

斜率优化，把 \min 去掉，转换成 z = y - kx 的形式：

dp_i - P_i Q_i = dp_j +s(Q_n - Q_j) - P_i Q_j

显然维护下凸壳。

但是，注意到 C_i 可能是 0，T_i 可能 <0，也就是说 Q_i 不具备严格单调性，P_i 不具有单调性。

我们依旧维护下凸壳，k 不具有单调性，但是我们可以在下凸壳上二分，加入点时注意 C_i = 0 的情况，防止三点共线的情况。

时间复杂度 O(n \log n)。

:::success[code]

#include <bits/stdc++.h>
#define int long long
#define ld long double
using namespace std;
const int MAXN = 3e5 + 10;
int head = 1, tail;
int q[MAXN], n, s;
int dp[MAXN], P[MAXN], Q[MAXN];
int X(int i) { return Q[i];}
int Y(int i) { return dp[i] - s * Q[i];}
ld slope(int i, int j) { 
    if (X(i) == X(j)) return 1e18; 
    return (ld)(Y(i) - Y(j)) / (ld)(X(i) - X(j));
}
int Search(int l, int r, ld x) {
    int L = l, R = r - 1, ans = -1;
    while (L <= R) {
        int mid = (L + R) >> 1;
        if (slope(q[mid], q[mid + 1]) >= x) ans = mid, R = mid - 1;
        else L = mid + 1;
    }
    if (ans == -1) return q[r];
    return q[ans];
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> s;
    for (int i = 1; i <= n; i++) {
        int t, c;
        cin >> t >> c;
        P[i] = P[i - 1] + t;
        Q[i] = Q[i - 1] + c;
    }
    memset(dp, 0x3f, sizeof(dp));
    dp[0] = 0;
    tail = 1;
    q[1] = 0; 
    for (int i = 1; i <= n; i++) {
        int pos = Search(head, tail, (ld)(P[i]));
        dp[i] = dp[pos] + (P[i] + s) * (Q[i] - Q[pos]) + s * (Q[n] - Q[i]);
        while (head < tail && slope(q[tail - 1], q[tail]) >= slope(q[tail], i)) tail--;
        q[++tail] = i; 
    }
    cout << dp[n];
    return 0;
}

:::

2.2.2 \text{P2900}

注意到对于 w_i\ge w_j, l_i\ge l_j 的土地 i, j，其中 j 显然没用。所以，在宽递减的情况下，长一定是递增的，所以先排个序。

显然，最终答案选的一定会是一段连续的区间。

设 dp_i 表示前 i 个矩阵的最小花费，则：

dp_i= \min_{j = 1}^i dp_{j - 1} + w_ih_j

如果 i < j 并且 i 的转移优于 j，则：

dp_{i - 1} + h_xw_i\le dp_{j - 1} + h_xw_b

也就是

h_x\le \frac{(-dp_{i - 1}) - (-dp_{j - 1})}{w_i - w_j}

显然可以维护一个下凸壳然后斜率优化。

:::success[code]

#include <bits/stdc++.h>
#define int long long
#define ld long double
using namespace std;
const int MAXN = 5e4 + 10;
int n;
int q[MAXN], head = 1, tail;
int dp[MAXN];
struct node {
    int x, y;
} a[MAXN];
bool cmp(node a, node b) {
    if (a.x == b.x) return a.y > b.y;
    return a.x > b.x;   
}
int X(int i) { return a[i + 1].x;} 
int Y(int i) { return dp[i];}
ld slope(int i, int j) { return (ld)(Y(i) - Y(j)) / (ld)(X(j) - X(i));}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
    sort(a + 1, a + n + 1, cmp);
    int tot = 0;
    for (int i = 1; i <= n; i++)
        if (a[i].y > a[tot].y) a[++tot] = a[i];
    n = tot;
    tail = 1;
    for (int i = 1; i <= n; i++) {
        while (head < tail && slope(q[head], q[head + 1]) <= (ld)(a[i].y)) head++;
        dp[i] = dp[q[head]] + a[q[head] + 1].x * a[i].y;
        while (head < tail && slope(q[tail - 1], q[tail]) >= slope(q[tail], i)) tail--;
        q[++tail] = i;
    }
    cout << dp[n];
    return 0;
}

:::

2.2.3 \text{P6302}

设 dp_i 表示乘坐第 i 班列车的最小烦躁值，当计算 dp_i 时已经计算完了所有到达城市 x_i 且到达的时刻 \le p_i 的列车，有：

dp_i = \min_{y_j = x_i\land q_j\le q_i} dp_j + A(p_i - q_j)^2 + B(p_i - q_j) + C

最终答案为

\min_{y_i = n} dp_i + q_i

斜率优化，去掉 \min，转化成 z = y - kx 的形式：

dp_i - (Ap_i^2 + Bp_i) = dp_j + Aq_j^2 - Bq_j + C - (p_i)(2Aq_j)

斜率和横坐标递增，使用单调队列维护下凸壳。

但是我们发现 y_j = x_i\land q_j\le q_i 这个限制不好维护。考虑第一个限制，我们注意到不同点之间互不影响，那么我们给每一个点开一个单调队列，在 x 位置查询。考虑第二个限制，将所有列车按照 p_i 排序后枚举时间，当时间到 p 再插入。

时间复杂度 O(n + m + \max q)。

:::success[code]

#include <bits/stdc++.h>
#define int long long
#define ld long double
using namespace std;
const int MAXN = 2e6 + 10;
const int inf = 1145141919810;
int n, m, A, B, C;
int ans = inf;
int id[MAXN], pos[MAXN];//id: 列车原编号->排序后位置; pos: b 数组索引->对应的 a 数组索引
int dp[MAXN], cnt[MAXN];//dp: 到达某列车(按 a 排序)的最小烦躁值; cnt: 到达某站点的列车数
int head[MAXN], tail[MAXN];
vector <int> v[MAXN];//每个站点的凸壳队列，存储 b 数组的索引 
struct node {
    int x, y;
    int p, q;
    int id;
} a[MAXN], b[MAXN];
bool cmp(node a, node b) { return a.p < b.p;}
bool cmp1(node a, node b) { return a.q < b.q;} 
int X(int i) { return 2 * A * b[i].q;}
int Y(int i) { return dp[pos[i]] + A * b[i].q * b[i].q - B * b[i].q;}
ld slope(int i, int j) {
    if (X(i) == X(j)) {
        if (Y(i) > Y(j)) return inf;
        else return -inf; 
    }
    return (ld)(Y(i) - Y(j)) / (ld)(X(i) - X(j));
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m >> A >> B >> C;
    memset(dp, -1, sizeof(dp));
    dp[0] = 0, dp[2000000] = inf;//0 号节点是虚拟起点，2000000 是虚拟哨兵
    pos[2000000] = 2000000;//哨兵映射到自己 
    for (int i = 1; i <= m; i++) {
        cin >> a[i].x >> a[i].y >> a[i].p >> a[i].q;
        a[i].id = i;
        cnt[a[i].y]++;
        b[i] = a[i];
    }
    sort(a + 1, a + m + 1, cmp);
    sort(b + 1, b + m + 1, cmp1);
    for (int i = 1; i <= n; i++) {
        v[i].resize(cnt[i] + 10);
        head[i] = tail[i] = 1;
        if (i > 1) v[i][1] = 2000000;
    }
    for (int i = 1; i <= m; i++) id[a[i].id] = i;
    for (int i = 1; i <= m; i++) pos[i] = id[b[i].id];
    int idx = 0;
    for (int i = 1; i <= m; i++) {
        while (idx < m && b[idx + 1].q <= a[i].p) {
            //将所有到达时间 <= 当前列车出发时间的列车加入凸壳 
            idx++;
            while (head[b[idx].y] < tail[b[idx].y] && slope(v[b[idx].y][tail[b[idx].y]], v[b[idx].y][tail[b[idx].y] - 1]) > slope(idx, v[b[idx].y][tail[b[idx].y]])) tail[b[idx].y]--;
            ++tail[b[idx].y];
            v[b[idx].y][tail[b[idx].y]] = idx;
        }
        while (head[a[i].x] < tail[a[i].x] && slope(v[a[i].x][head[a[i].x] + 1], v[a[i].x][head[a[i].x]]) <= (ld)(a[i].p)) ++head[a[i].x];
        dp[i] = dp[pos[v[a[i].x][head[a[i].x]]]] + A * (a[i].p - b[v[a[i].x][head[a[i].x]]].q) * (a[i].p - b[v[a[i].x][head[a[i].x]]].q) + B * (a[i].p - b[v[a[i].x][head[a[i].x]]].q) + C;
        if (a[i].y == n) ans = min(ans, dp[i] + a[i].q);
    }
    cout << ans;
    return 0;
}

:::

2.2.4 \text{P4655}

设 dp_i 表示保留第 i 根柱子的最小代价，s_i = \sum_{j = 1}^i w_i，则：

dp_i = \min_{j = 1}^{i - 1} dp_j + (h_i - h_j)^2 + s_{i - 1} - s_j

这是斜率式，但是 x_j = 2h_j 和 k = h_i 都没有单调性。有以下两种常用维护做法（其实还有平衡树，但是懒得写了 qwq）：

\text{CDQ} 分治

套路的将转移方程拆开平方并化成 z = y - kx 的形式：

dp_i - s_{i - 1} - h_i^2 = dp_j + h_j^2 - s_j - 2h_ih_j

显然维护下凸壳。

考虑 \text{CDQ} 分治步骤：

时间复杂度：O(n\log n)。

代码没写。

李超线段树

将转移方程拆开平方并化简：

dp_i = h_i^2 + s_{i - 1} + \min_{j = 1}^{i - 1} dp_j - 2h_ih_j + h_j^2 - s_j

观察李超线段树的作用：有多条线段，求单点最值。

于是令 i 对应单点，j 对应直线，把每个 dp_i 求出后添加一条直线。

那么，令 a_j = -2h_j, b_j = dp_j + h_j^2 - s_j，将问题转换为：插入直线 y_j = a_jx + b_j，求 x = h_i 时 y_j 最小值，使用李超线段树。

时间复杂度：O(n\log n)。

:::success[code]

#include <bits/stdc++.h>
#define int long long
#define db double
#define pii pair <int, int>
#define fi first
#define se second
using namespace std;
const int MAXN = 2e6 + 10;
const int N = 1e6;
const db eps = 1e-9;
int n;
int a[MAXN], b[MAXN];
int h[MAXN], W[MAXN], s[MAXN];
int dp[MAXN];
int cmp(int a, int b) {
    if (a - b > 0) return -1;
    if (b - a > 0) return 1;
    return 0;
} 
int w[MAXN];    
int tot;
db calc(int id, int d) { return a[id] * d + b[id];}
void upd(int u, int l, int r, int x) {
    if (w[u] == 0) { 
        w[u] = x;
        return;
    }
    if (l == r) {
        if (calc(x, l) < calc(w[u], l)) w[u] = x;
        return;
    }
    int y = w[u];
    int mid = (l + r) >> 1;
    int bmid = cmp(calc(x, mid), calc(y, mid));
    if (bmid == 1) {
        swap(w[u], x);
        y = w[u];
    }
    int L = cmp(calc(x, l), calc(y, l)), R = cmp(calc(x, r), calc(y, r));
    if (L == 1) upd(u << 1, l, mid, x);
    else if (R == 1) upd(u << 1 | 1, mid + 1, r, x);
}
pii Min(pii a, pii b) {
    if (cmp(a.fi, b.fi) == 1) return a;
    else if (cmp(a.fi, b.fi) == -1) return b;
    else return a.se < b.se ? a : b;
}
pii query(int u, int l, int r, int d) {
    if (r < d || l > d) return {2e18, 0};
    int mid = (l + r) >> 1;
    int res = calc(w[u], d);
    if (l == r) return {res, w[u]};
    return Min({res, w[u]}, Min(query(u << 1, l, mid, d), query(u << 1 | 1, mid + 1, r, d)));
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    b[0] = 2e18;
    for (int i = 1; i <= n; i++) cin >> h[i];
    for (int i = 1; i <= n; i++) {
        cin >> W[i];
        s[i] = s[i - 1] + W[i];
    }
    a[1] = -2 * h[1], b[1] = 0 + h[1] * h[1] - s[1];
    upd(1, 0, N, 1);
    for (int i = 2; i <= n; i++) {
        dp[i] = h[i] * h[i] + s[i - 1] + query(1, 0, N, h[i]).fi;
        a[i] = -2 * h[i], b[i] = dp[i] + h[i] * h[i] - s[i];
        upd(1, 0, N, i);
    }
    cout << dp[n];
    return 0;
}

:::

2.3 习题

3. 决策单调性优化 \text{DP}

3.1 基础定义

对于一维 DP：

dp_i = \min_{j = 1}^{j < i} dp_j + w(j, i)

我们记每一个点 i 的最优决策点为 \operatorname{opt}(i)（可能是一个集合，通常使用最左 / 右元素比较）。

如果 \operatorname{opt}(i) 随着 i 单调变化，称该 DP 有决策单调性。

3.2 四边形不等式

定义 1：已知 w(i, j) (1\le i < j\le n)，若对任意 x_1\le x_2\le y_1\le y_2，有 w(x_1, y_1) + w(x_2, y_2)\le w(x_1, y_2) + w(x_2, y_1)，则称该函数满足四边形不等式。 简单记为：交叉小于包含。

定义 2：若对任意 x, y(x\le y)，有 w(x, y) + w(x + 1, y + 1)\le w(x, y + 1) + w(x + 1, y)。

定理：对于 DP 式 f，若其 w 满足四边形不等式，则 f 满足决策单调性。

:::info[定理的证明] 考虑反证法。

我们假设 i > j 并且 \operatorname{opt}(i) < \operatorname{opt}(j)。

根据 f 的定义，有：

f_{\operatorname{opt}(i)} + w(\operatorname{opt}(i), i)\le f_{\operatorname{opt}(j)} + w(\operatorname{opt}(j), i)\\

由于 \operatorname{opt}(i) < \operatorname{opt}(j) < j < i，由四边形不等式可得：

w(\operatorname{opt}(i), j) + w(\operatorname{opt}(j), i)\le w(\operatorname{opt}(i), i) + w(\operatorname{opt}(j), j)

与前面的式子相加得：

f_{\operatorname{opt}(i)} + w(\operatorname{opt}(i), j)\le f_{\operatorname{opt}(j)} + w(\operatorname{opt}(j), j)

对于 j，\operatorname{opt}(i) 是一个更优的决策点，与原假设矛盾，故单调性成立。

证毕。 :::

3.3 优化

若 DP 满足决策单调性，可以采用以下优化。

3.3.1 分治

适用于方程不含 f_j 的情况。

我们定义 \text{solve}(l, r, L, R)，表示当前分治状态点区间为 [l, r]，决策点区间为 [L, R]。

首先，设中点 mid = \frac{l + r}{2}，先扫一遍 [L, R] 求出当前最优决策点 \operatorname{opt}(mid)。

根据决策单调性，计算 [l, mid) 时决策点一定在 [L, \operatorname{opt}(mid)]，计算 (mid, r] 时决策点一定在 [\operatorname{opt}(mid), R]，于是分治下去即可。

显然复杂度为 O(n\log n)。

:::success[code]

void solve(int l, int r, int L, int R) {
    if (l > r) return;
    int mid = (l + r) >> 1, p = 1;
    for (int i = L; i <= min(mid, R); i++)
        if (w(i, mid) > dp[mid]) dp[mid] = w(i, mid), p = i;
    solve(l, mid - 1, L, p);
    solve(mid + 1, r, p, R);
}

:::

3.3.2 二分队列

适用于“半在线”的情况。

由于每个决策点更新范围是一个连续区间，所以相邻决策点存在一个分界线 k，当 i > k 时，前一个决策点再也不可能更新了。

于是我们用一个队列 q 维护当前候选决策点，一个 k 维护每个决策点开始成为最优的起始位置。

当加入一个 i，有以下步骤：

:::success[code]

int Search(int x, int y) {
    int l = x,  r = n + 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (calc(mid, x) >= calc(mid, y)) r = mid;
        else l = mid + 1;
    }
    return l;
}
for (int i = 1; i <= n; i++) {
    while (head < tail && k[head] <= i) head++;
    dp[i] = calc(i, q[head]);
    opt[i] = q[head];
    while (head < tail && k[tail - 1] >= Search(q[tail], i)) tail--;
    k[tail] = Search(q[tail], i);
    q[++tail] = i; 
}

:::

3.4 例题

3.4.1 \text{P3515}

显然，题目中让我们求 \max_{j = 1}^n a_j + \sqrt{|i - j|} - a_i。

这个绝对值很烦，考虑分成 j\le i 和 j > i 两部分算，考虑 j\le i 的情况怎么算，显然另一种区间翻转即可。

我们设 dp_i = \max_{j = 1}^i a_j + \sqrt{i - j} - a_i，注意到 dp_i 有决策单调性。

:::info[证明] 对于 i < j，设 w(i, j) = -(a_i - a_j + \sqrt{i - j})。

将 w(i, j) 带入四边形不等式

-(a_{x_1} - a_{y_1} + \sqrt{y_1 - x_1}) -(a_{x_2} - a_{y_2} + \sqrt{y_2 - x_2})\le -(a_{x_1} - a_{y_2} + \sqrt{y_2 - x_1}) -(a_{x_2} - a_{y_1} + \sqrt{y_1 - x_2})\\ -\sqrt{y_1 - x_1} - \sqrt{y_2 - x_2}\le -\sqrt{y_2 - x_1} - \sqrt{y_1 - x_2}\\ \sqrt{y_1 - x_1} + \sqrt{y_2 - x_2}\ge \sqrt{y_2 - x_1} - \sqrt{y_1 - x_2}

两边平方一下：

y_1 - x_1 + y_2 - x_2 + 2\sqrt{(y_1 - x_1)(y_2 - x_2)}\ge y_2 - x_1 + y_1 - x_2 + 2\sqrt{(y_2 - x_1)(y_1 - x_2)}

化简：

(y_1 - x_1)(y_2 - x_2)\ge (y_2 - x_1)(y_1 - y_2)\\ y_1y_2 + x_1x_2 - x_1y_2 - x_2y_1\ge y_1y_2 + x_1x_2 - x_1y_1 - x_2y_2\\ -x_1y_2 - x_2y_1\ge - x_1y_1 - x_2y_2\\ (x_1 - x_2)(y_2 - y_1)\le 0

因为 x_1\le x_2, y_1\le y_2，上式显然成立，那么原函数满足四边形不等式。 :::

然后套模板分治即可。

:::success[code]

#include <bits/stdc++.h>
#define int long long
#define db double
using namespace std;
const int MAXN = 5e5 + 10;
int n, a[MAXN];
db dp[MAXN];
db w(int j, int i) { return (db)(a[j]) + sqrt(i - j);}
void solve(int l, int r, int L, int R) {
    if (l > r) return;
    int mid = (l + r) >> 1, p = 1;
    for (int i = L; i <= min(mid, R); i++)
        if (w(i, mid) > dp[mid]) dp[mid] = w(i, mid), p = i;
    solve(l, mid - 1, L, p);
    solve(mid + 1, r, p, R);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    solve(1, n, 1, n);
    reverse(a + 1, a + n + 1);
    reverse(dp + 1, dp + n + 1);
    solve(1, n, 1, n);
    for (int i = n; i >= 1; i--) cout << (int)ceil(dp[i]) - a[i] << '\n';
    return 0;
}

:::

3.4.2 \text{P6932}

对于两家生产公司 i, j，如果 d_i\le d_j, p_i\le p_j，那么和第 j 家生产公司签订合同永远是亏的，那么不考虑第 j 家生产公司；同理，对于两家消费公司 i, j，如果 e_i\le e_j, q_i\le q_j，那么和第 i 家消费公司签订合同永远是亏的，所以不考虑第 i 家消费公司。

处理后生产公司按 d 升序排列，p 严格降序；处理后的消费公司按 e 升序排列，q 严格降序。

我们定义利润函数 w(i, j)= (e_j - d_i)(q_j - p_i)，可以看出 w 满足决策单调性，也就是对于 j_1 < j_2，都有 \operatorname{opt}(j_1)\le \operatorname{opt}(j_2)。

::::info[证明]

对于所有 i_1 < i_2, j_1 < j_2，四边形不等式成立：

w(i_1, j_2) + w(i_2, j_1)\le w(i_1, j_1) + w(i_2, j_2)

我们定义差值：

\Delta = w(i_1, j_1) + w(i_2, j_2) - w(i_1, j_2) - w(i_2, j_1)

对于四边形不等式成立，就是 \Delta \ge 0。

我们将 w 带入 \Delta 并化简：

\begin{aligned} \Delta &= (e_{j_1} - d_{i_1})(q_{j_1} - p_{i_1}) + (e_{j_2} - d_{i_2})(q_{j_2} - p_{i_2}) - (e_{j_2} - d_{i_1})(q_{j_2} - p_{i_1}) - (e_{j_1} - d_{i_1})(q_{j_1} - p_{i_2}) \\ &= -e_{j_1}p_{i_1} - e_{j_2}p_{i_2} + e_{j_2}p_{i_1} + e_{j_1}p_{i_2} - d_{i_1}q_{j_1} - d_{i_2}q_{j_2} + d_{i_1}q_{j_2} + d_{i_2}q_{j_1}\\ &= (e_{j_2} - e_{j_1})(p_{i_1} - p_{i_2}) + (q_{j_2} - q_{j_1})(d_{i_1} - d_{i_2}) \end{aligned}

由于 e 是升序的，所以 e_{j_2}\ge e_{j_1}, e_{j_2} - e_{j_1}\ge 0，其他同理，按照数组单调性判断符号即可。

判断完可以发现，对于第一项 (e_{j_2} - e_{j_1})(p_{i_1} - p_{i_2})\ge 0，第二项 (q_{j_2} - q_{j_1})(d_{i_1} - d_{i_2})\ge 0，那么 \Delta\ge 0，原式满足四边形不等式。

证毕。 ::::

套模板分治即可。

::::success[code]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int MAXN = 5e5 + 10;
int n, m, dp[MAXN];
struct node {
    int x, y;
} a[MAXN], b[MAXN];
bool cmp1(node a, node b) {
    if (a.x == b.x) return a.y < b.y;
    return a.x < b.x;
}
bool cmp2(node a, node b) {
    if (a.x == b.x) return a.y > b.y;
    return a.x > b.x;
}
int w(int i, int j) { 
    if (b[i].x <= a[j].x || b[i].y <= a[j].y) return 0;
    return (b[i].x - a[j].x) * (b[i].y - a[j].y);
}
void solve(int l, int r, int L, int R) {
    if (l > r) return;
    int mid = (l + r) >> 1, p = R;
    for (int i = L; i <= R; i++)
        if (w(i, mid) > dp[mid]) dp[mid] = w(i, mid), p = i;
    solve(l, mid - 1, p, R);
    solve(mid + 1, r, L, p);
}
signed main() {
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i].x >> a[i].y;
    sort(a + 1, a + n + 1, cmp1);
    int tot = 1;
    for (int i = 2; i <= n; i++)
        if (a[i].y < a[tot].y) a[++tot] = a[i];
    n = tot;
    for (int i = 1; i <= m; i++) cin >> b[i].x >> b[i].y;
    sort(b + 1, b + m + 1, cmp2);
    tot = 1;
    for (int i = 2; i <= m; i++)
        if (b[i].y > b[tot].y) b[++tot] = b[i];
    m = tot;
    solve(1, n, 1, m);
    int ans = 0;
    for (int i = 1; i <= n; i++) ans = max(ans, dp[i]);
    cout << ans;
    return 0;
}

::::

3.4.3 \text{P1912}

设 len_i 为第 i 个字符串的长度，s_i = \sum_{j = 1}^i len_j + i，dp_i 表示前 i 句的最小代价，则：

dp_i = \min_{k = 0}^{i - 1} dp_j + |s_i - s_j - L - 1|^p

注意到 dp_i 有决策单调性

:::info[证明]

若代价函数 w(j, i) 满足四边形不等式：

a < b < c < d, w(a, d) + w(b, c) \ge w(a, c) + w(b, d)

则最优决策点 \operatorname{opt}(i) 单调不减。

验证 w(j, i) = |s_i - s_j - L - 1|^p 满足四边形不等式。根据四边形不等式判定定理，若对任意 j < i 有：

w(j + 1, i) + w(j, i + 1) \ge w(j, i) + w(j + 1, i + 1)

则 w 满足四边形不等式。移项得：

w(j + 1, i) - w(j + 1, i + 1) \ge w(j, i) - w(j, i + 1)

令 u = s_i - s_j - L - 1，v = s_i - s_{j+1} - L - 1，则 u > v。代入 w 的定义，上式等价于：

|v|^p - |v + len_{i + 1}|^p \ge |u|^p - |u + len_{i + 1}|^p

令 c = len_{i+1} > 0，f(x) = |x|^p - |x + c|^p，可以证明 f(x) 在 \mathbb{R} 上单调不递增。因为 u > v，所以 f(v) \ge f(u)，即：

|v|^p - |v + c|^p \ge |u|^p - |u + c|^p

故原不等式成立，由判定定理知 w 满足四边形不等式。综上，四边形不等式成立，决策点 \operatorname{opt}(i) 单调不减。

证毕。 :::

然后套模板二分队列即可。

:::success[code]

#include <bits/stdc++.h>
#define int long long
#define ld long double
using namespace std;
const int MAXN = 1e5 + 10;
int n, l, p;
int s[MAXN], q[MAXN], k[MAXN], opt[MAXN];
ld dp[MAXN];
string str[MAXN];
ld qpow(ld a, int b) {
    ld res = 1;
    while (b) {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
ld calc(int i, int j) { return dp[j] + qpow(abs(s[i] - s[j] - l), p);}
int Search(int x, int y) { 
    int l = x,  r = n + 1;
    while (l < r) {
        int mid = (l + r) >> 1;
        if (calc(mid, x) >= calc(mid, y)) r = mid;
        else l = mid + 1;
    }
    return l;
}
signed main() {
    int T;
    cin >> T;
    while (T--) {
        cin >> n >> l >> p;
        l++;
        for (int i = 1; i <= n; i++) {
            cin >> str[i];
            s[i] = s[i - 1] + str[i].size() + 1;
        }
        int head = 1, tail = 0;
        tail++;
        q[1] = 0;
        k[1] = 0;
        for (int i = 1; i <= n; i++) {
            while (head < tail && k[head] <= i) head++;
            dp[i] = calc(i, q[head]);
            opt[i] = q[head];
            while (head < tail && k[tail - 1] >= Search(q[tail], i)) tail--;
            k[tail] = Search(q[tail], i);
            q[++tail] = i; 
        }
        if (dp[n] > 1e18) {
            cout << "Too hard to arrange\n--------------------\n";
            continue;
        }
        printf("%.0Lf\n", dp[n]);
        tail = 0;
        q[0] = n;
        for (int i = n; i; i = opt[i]) q[++tail] = opt[i];
        for (; tail; tail--) {
            for (int i = q[tail] + 1; i < q[tail - 1]; i++) cout << str[i] << ' ';
            cout << str[q[tail - 1]] << '\n';
        }
        cout << "--------------------\n";
    }
    return 0;
}

:::

3.5 习题