一些动态规划的优化算法：斜率优化、四边形不等式、Slope Trick、wqs二分

斜率优化

考虑我们求解的问题可以简化为：

$$f_i=\min(f_j-j\times a_i)$$

令 $f_i=b,f_j=y,a_i=k$，则：

$$b=y-kx\\ \Rightarrow y = kx + b$$

其中 $(x,y)$ 是本来就有的点（而且有很多个，均为备选项），$b$ 为我们要求的东西，我们希望 $b$ 最小。

显然，合法的/可选的点构成一个下凸壳。$k$ 是我们当前有的，我们只需要找到相切的情况，就可以确定 $b$ 了。

• 如果满足决策单调性，由于在凸包上，我们可以直接双指针
• 如果凸包是静态的，我们也可以直接在凸包上二分
• 如果凸壳不是静态的，可以用平衡树维护
• 不想用平衡树的话，可以直接离线处理然后分治。因为加入了时间戳这一个维度，我们可以使用cdq分治

四边形不等式优化

使用条件：

当 $a\le b\le c\le d$ 时：

$$w(a,c)+w(b,d)\le w(a,d)+w(b,c)$$

这看起来好像很复杂，但我们往往可以直接让 $b=c$，那样子就等价于区间合并比区间单独更优。

如果满足四边形不等式，必然满足决策点单调性：

设 $i$ 是由 $opt_i$ 转移过来的，必然有 $opt_i\le opt_{i+1}$

注意，决策点单调性不等于可以用双指针，例如：

我们可以使用分治的方法。

假设我们现在处理第 $k$ 层的问题，在转移 $(l,r,L,R)$ ，即转移 $(l,r)$ 内，其决策点在 $(L,R)$ 范围内。

我们可以先暴力算出 $mid$ 的转移点。然后分治 $(l,mid-1,L,opt_{mid})$ 与 $(mid+1,r,opt_{mid},R)$

CF868F

给定一个长度为 n 的序列 a，要求将其恰好划分为 k 个连续的非空子段。每个子段 [l, r] 的代价是该子段内相同元素的对数。求所有子段代价之和的最小值

首先有 $w(l,k)+w(k,r)\le w(l,r)+(w(k,k)=0)$，满足四边形不等式和决策点单调性

设 $f(i,j)$ 表示前 $i$ 个点划分 $j$ 的代价之和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

// dp_cur[i] 代表当前层 dp[i]
// dp_pre[i] 代表上一层 dp[i]
// 代价函数 区间代价(l, r)：靠全局指针动态维护，均摊单次O(1)
函数 分治求解(左边界l, 右边界r, 最优解左限optL, 最优解右限optR):

    // 遍历所有可行分割点，找mid位置的最优解
    遍历上限k_max = 取较小值(optR, mid - 1)
    循环 k 从 optL 到 k_max:
        当前总代价 = dp_pre[k] + 区间代价(k, mid)
        如果 当前总代价 < bestVal:
            bestVal = 当前总代价
            bestK = k

    // 更新当前层mid位置的dp值
    dp_cur[mid] = bestVal

    // 决策单调性分治递归处理左右区间
    分治求解(l, mid - 1, optL, bestK)
    分治求解(mid + 1, r, bestK, optR)

Slope Trick

如果我们维护的函数是一个凸函数，我们可以直接维护其拐点

直接拿题来讲：

P4597

给定一个序列，每次操作可以把某个数 $+1$ 或 $−1$。要求把序列变成非降数列。

显然有：

$$f_{i,x}=\min_{k\le x}(f_{i-1,k})+|a_i-x|$$

我们定义三个函数：

• $F(x)$，和上面一样
• $G(x)=\min_{y\le x}F(y)$
• $H(x)=|a_i-x|$

我们可以证明 $F(x)$ 是下凸的。

考虑数学归纳法

若 $F(x)$ 是下凸的，那样子 $G(x)$ 显然是凸的。

而 $H(x)$ 也是下凸的。

所以 $F(x)=G(x)+H(x)$

我们每次转移需要的就是下凸的点（那样子代价就最小）。

我们考虑用大根堆来维护，由于最低点的右边没用，所以我们可以不维护。

我们那大根堆直接来维护拐点，相当于就是在维护凸壳。后面有几个点，那样子斜率就是多少。

我们考虑现在加入 $H(x)$，即 $|a_i-x|$

那我们需要让所有 $a_i$ 之前的点斜率的绝对值+1，$a_i$ 之后的点斜率的绝对值-1

斜率的变化必须使用点来维护。

对于 $a_i$ 之前的点斜率+1，我们插入一个 $a_i$ 即可。

对于 $a_i$ 之后的点，要使其斜率-1。我们考虑差分。删掉末尾的点，然后再插入一个 $a_i$。

删掉末尾的点可行的原因是：

1. 可以使后面那堆点后面点的数量-1，即斜率绝对值-1
2. 而这个点本身再往后的线段的斜率已经为负，可以大胆去掉

注意，我们要先加入 $a_i$，再计算代价，最后再删点。因为如果 $a_i$ 过大，那就是满足题意，而我们删掉的，也是 $a_i$ 本身。

1
2
3
4
5
6
7
8
9
10

输入n
初始化大根堆q
ans = 0
循环i从1到n:
    读取x
    将x两次入堆
    y = 堆顶元素
    弹出堆顶
    ans = ans + |x - y|
输出ans

wqs二分

wqs二分用于解决以下类型的问题：

题目中有某类限制。去掉此限制很容易。同时结果关于此限制是凸的。

例：背包问题，大小为 $V$，恰好选 $m$ 个

没有 $m$ 是好做的。

于是我们可以二分一个代价 $k$，每个物品的价值为 $val_i'=val_i-k$，然后再去做背包。

在这种状态下，我们求得的最优解用了 $i$ 个物品。

• 如果 $i<m$，那么代价太大了，把 $k$ 调小
• 如果 $i>m$，那么代价太小了，把 $k$ 调大

边界处理：

我们可能会遇到最后一段是一条直线的情况（即对于同一个 $k$，有多个合法的 $m$）

那样子我们可以直接把 $k$ 拿出来，在外面跑一次，那样子就可以求出最大价值了。