DDOSvoid's Blog

DP的优化

发表于 更新于 分类于
本文字数： 8.9k 阅读时长 ≈ 8 分钟

简介

大概会介绍几种常见的优化 $dp$ 的方法 = =

弱化条件优化

这个做法只能用于最优化问题，大概我们通过减弱题目的条件来多求得一些更差的状态但是我们仍然能求得最优的状态

例题

  1. 简要题意：给定 $n$ 个数轴上的点，以及每个点可以延伸的长度，现在每个点只能向左或者右一个方向延伸，求这 $n$ 个延伸出的线段的并的最大值

    $n\le 100$

    简要题解：首先将所有点按照位置排序，然后我们考虑一个比较简单的 $DP$，我们令 $f[i][j][k]$表示前 $i$ 条线段，最靠右的线段为 $j$，方向为 $k$，然后我们考虑如何转移到第 $i+1$ 条线段，发现这种情况下会算错

    无标题.png

    这种情况下，我们发现 $j$ 这个线段完全被包含了，也就是说他是没有贡献的

    所以我们考虑换一个转移方式，那么我们考虑直接从 $i$ 转移到下一个线段 $j$，然后我们认为 $k\in [i+1,j-1]$ 的线段都没有贡献，注意到这样的答案只会变小，只需要考虑最优答案是否能被计算，然后我们发现这种情况好像算不到

    111.png

    我们的解决方案就是对于 $k\in[i+1,j-1]$ 的线段贪心向右延伸，时间复杂度 $O(n^3)$

    CF 559E Gerald and Path

观察答案形式优化

大概就是最优解的答案一定能转换成某种形式，这种形式可以快速求解

例题

  1. 注意到我们一定能将最优解的划分变成只有 $1$ 和 $c$​ 两种

    CF 940E Cashback

  2. 简要题意：给定一个长为 $n$ 的序列 $a$，需要将 $a$ 划分成若干段，使得所有段的代价和最小，一段的代价定义为这一段中不同的数字的种数的平方

    简要题解：

    注意到答案的上界为 $n$​，那么一个长度为 $len$​ 的区间的不同数字的种数不能超过 $\sqrt {len}$​，否则一定不优

    另外还能发现 $f$ 一定单调不降，所以我们只需要记录 $O(\sqrt n)$ 最靠左的满足数字种数不超过 $k,k\in[1,\sqrt n]$ 的端点即可

    总的时间复杂度就是 $O(n\sqrt n)$​

    Luogu P2943 [USACO09MAR]Cleaning Up G

观察状态转移优化

不知道这样说是不是对的

有一类题目的状态转移要求复杂，想要根据状态转移的限制进行优化需要使用大量数据结构

但有时能通过状态之间的联系找到更简单的优化方式

例题

[]

观察决策点优化

在某些题目中，决策点和其可以转移到的点之间可能有一些微妙的性质，我们通过对这些性质的分析来进行优化

例题

  1. 简要题意：给定 $n$​ 和 $m$​ 个素数 $P$​，对于一个数 $x$​，每次可以选择一个 $p_i$​，将 $x$​ 变成 $x-x\bmod p_i$​，令 $f_i$​ 表示将 $i$​ 变成 $0$​ 的最小步数，求 $\sum_{i=1}^nf_i\times 23333^{n-i}\bmod 2^{64}$​

    $n\le 2\times 10^6,|P|\le 10^5,T\le 15$​

    容易发现 $O(n\log n)$ 的算法是不能通过的

    我们考虑对于 $x$​，$x$​ 能够成为决策点的条件是至少存在一个 $p\in P$​，且 $p|x$，另外能够注意到 $x$ 可以转移到的点为 $[x+1,x+p-1]$，其中 $p$ 是最大的整除 $x$，且属于给定素数集的素数

    另外容易发现 $f_i$ 单调不降，能够发现 $dp$ 一定存在决策单调性，且每个决策点能转移到的点是自己后面一段区间，所以我们直接 $dp$​，同时维护当前决策点，当前决策点失效时暴力右移即可，时间复杂度 $O(n)$

    2021CCPC网络赛 L Remove

矩阵快速幂优化

矩阵快速幂一般是用来优化常系数线性递推的，但是某些题的转移也是可以写成矩阵的形式的

例题

  1. 简要题意：现在有一块长为 $L$ 的巧克力，我们可以将其切成若干段，不妨假设切成了 $m$ 段，每段的长度为 $a_i$，那么这种切法的价值就是 $\sum_{i=1}^ma_i^2$，现在给定 $n$ 个位置，这些位置不能切，求所有切法的价值和，答案对 $1e9+7$ 取模

    $L\le 10^9,n\le 10^5$

    简要题解：我们考虑 $dp$，令 $f_i$ 表示切的位置在 $i$ 的价值和，容易得到 $f_i=\sum_{j=0}^{i-1}f_j(i-j)^2$

    这个东西咋一看没法优化，但其实这个东西可以写成矩阵的形式，我们考虑用矩阵维护 $\sum_{i=0}^nf_i,\sum_{i=0}^n(n+1-i)f_i,\sum_{i=0}^n{(n+1-i)^2f_i}$，然后发现三个东西可以转移的，转移矩阵为

    注意这个转移矩阵是左乘的，然后没法切的转移就是将第三列都减掉一个 $1$，时间复杂度 $O(n\log n)$

    【个人赛组】2021-2022年度第三届全国大学生算法设计与编程挑战赛（秋季赛） G 巧克力

单调队列优化

一句话总结，式子能用单调队列优化的就能用单调队列优化（套娃？

举个栗子

1
2
3
for (int i = 1; i <= n + 1; ++i) 
    for (int j = max(0, i - m - 1); j <= i - 1; ++j)
        f[i] = max(f[i], f[j] + s[i - 1] - s[j]);

我们稍微转换一下能够得到 $f_i = s_{i-1}+max\{f_j-s_j\}$

其中 $i-j-1\le m$，后面那一坨与 $i$ 没关系且是一个滑动窗口，所以可以用单调队列进行优化

例题

Luogu P2034 选择数字

决策单调性优化

决策单调性优化适用于 $1D/1D$ 动态规划

简单来讲，我们令 $g_i$ 表示 $f_i$ 是由 $f_{g_i}$ 转移而来的，如果我们说 $f$ 的转移满足决策单调性，则意味着 $g_i \ge g_j(i>j)$

四边形不等式

定义：对于一个定义在整数集上的二元函数 $w(x,y)$，我们称该不等式为 $\forall a<b<c<d,w(a,c)+w(b,d)\le w(a,d)+w(b,c)$ 四边形不等式

若二元函数 $w(x,y)$ 满足 $\forall a<b,w(a,b)+w(a+1,b+1)<w(a,b+1)+w(a+1,b)$，则 $w(x,y)$ 满足四边形不等式

对于一个 $1D/1D$ 动态规划，我们定义 $w(x,y)$ 为将 $x$ 作为 $y$ 的决策点的代价，如果该二元函数满足四边形不等式，则该动态规划一定满足决策单调性

证明：https://www.luogu.com.cn/blog/83547/zong-dong-tai-gui-hua-di-ben-zhi-kan-si-bian-xing-fou-deng-shi-you-hua

大概讲一下，我们以 Luogu P3195 [HNOI2008]玩具装箱TOY 为例

我们使用反证法，假设 $\exists i < j , g_i > g_j$，即 $g_j<g_i<i<j$

我们令 $w(x,y)=(s_y-s_x-L)^2$，那么我们有 $f_{g_i}+w(g_i, i)<f_{g_j}+w(g_j,i)$ 和 $f_{g_j}+w(g_j,j)<f_{g_i}+w(g_i,j)$

两式相加，我们能够得到 $w(g_i,i)+w(g_j,j)<w(g_j,i)+w(g_i,j)$

由于是反证，所以我们只需要证明 $w(g_i,i)+w(g_j,j)\ge w(g_j,i)+w(g_i,j)$，发现这个东西正是四边形不等式

那么如果要证明该题满足决策单调性，只需要证明 $\forall a<b,w(a,b)+w(a+1,b+1)\le w(a,b+1)+w(a+1,b)$

算法

单调队列

根据决策单调性，每一个 $x$ 能做的转移是一段区间，且随着 $x$ 的增大，区间逐渐靠右且不相交，大概是这个样子 $1122222333455566$

我们拿一个单调队列来维护这个东西，考虑一个 $x$ 入栈，如果 $x$ 的转移在栈顶所能转移的区间的左端点更优，则显然可以直接扔掉队尾，否则直接二分

但是这个东西复杂度正确当且仅当 $w_{x,y}$ 可以 $O(1)$ 计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
inline ll w(int x, int y) {
    // 用 x 来更新 y
} 

struct node {
    int l, r, k;
};

int main() { 
    deque<node> Q; Q.push_back({ 1, n, 0 });
    for (int i = 1; i <= n; ++i) {
        while (!Q.empty() && Q.front().r < i) Q.pop_front();
        f[i] = w(Q.front().k, i);
        while (!Q.empty() && w(Q.back().k, Q.back().l) >= w(i, Q.back().l)) Q.pop_back();
        int l = Q.back().l, r = Q.back().r, k = Q.back().k, mid, ans;
        while (l <= r) {
            mid = l + r >> 1;
            if (w(k, mid) < w(i, mid)) ans = mid, l = mid + 1; 
            else r = mid - 1; 
        } Q.back().r = ans; if (ans < n) Q.push_back({ ans + 1, n, i });
    } cout << f[n] << endl; 
}

分治

分治的做法类似于整体二分，令 $solve(l, r, L, R)$ 表示 $[l,r]$ 的决策点在 $[L,R]$

我们每次取 $[l,r]$ 的中点 $m$，然后扫 $[L,R]$ 找 $m$ 的决策点 $p$，然后递归处理

一共 $\log n$ 层，每层的复杂度都是 $n$

这样做的优势在于可以用类似莫队的方法累加来求 $w_{x,y}$

缺点在于转移不按照顺序，必须保证 $f_i$ 和 $g_j$ 之间没有关系

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int cnt[maxn], l, r; ll sum;
inline void add(int x) { sum += cnt[x]++; }
inline void del(int x) { sum -= --cnt[x]; } 
void move(int L, int R) {
    while (r < R) add(a[++r]);
    while (l > L) add(a[--l]);
    while (r > R) del(a[r--]);
    while (l < L) del(a[l++]);
}

ll f[maxn], g[maxn]; 
void solve(int l, int r, int L, int R) { // f_i in [l, r], g_j in [L, R] 
    if (l > r) return ; int m = l + r >> 1, p = L;
    for (int i = L; i <= min(R, m - 1); ++i) {
        move(i + 1, m);
        if (g[i] + sum < f[m]) f[m] = g[i] + sum, p = i;
    }
    solve(l, m - 1, L, p); solve(m + 1, r, p, R);
}

例题

  1. 简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和一个正整数 $L$，现在需要将这个序列划分成若干连续段，对于 $[l,r]$ 这一段，其长度定义为 $len=r-l+\sum_{i=l}^ra_i$，其代价为 $(len-L)^2$，求最小代价和

    $n\le 5\times 10^4$

    简要题解：容易得到朴素 $dp$ 为 $f_i = max\{f_j+(i-j+1-L+s_i-s_j)^2\}$

    由于某种神秘力量，我们得知 $f$ 的转移满足决策单调性

    且 $w_{x,y}$ 可以 $O(1)$ 计算，所以我们直接使用单调栈来进行决策单调性优化即可，时间复杂度 $O(n\log n)$

    Luogu P3195 [HNOI2008]玩具装箱TOY

  2. 简要题意：给定一个长度为 $n$ 的序列 $a_i$，对于每个 $i\in[1,n]$，求一个最小的非负整数 $p$，满足对于所有 $j\in [1,n]$，$p\ge a_j+\sqrt {|i-j|}-a_i$

    $n\le 5\times 10^5$

    简要题解：容易得到 $dp$ 方程，$f_i=max\lbrace a_j+\sqrt{i-j}\rbrace -a_i$，这里仅考虑 $ji$ 的情况直接将数组翻转然后再做一遍即可，容易发现该转移满足决策单调性

    证明：

    我们只需要证明 $\forall a<b,w(a,b)+w(a+1,b+1)\ge w(a,b+1)+w(a+1,b)$，此题中 $w(x,y)=\sqrt{y - x}$

    即只需要证明 $\sqrt{b-a}+\sqrt{b-a}\ge \sqrt{b+1-a}+\sqrt{b-1-a}$，令 $d=b-a$

    得 $2\sqrt d\ge \sqrt{d+1}+\sqrt{d-1}$，化简得 $\sqrt{d}-\sqrt{d-1}\ge \sqrt{d+1}-\sqrt{d}$ 得证

    P3515 [POI2011]Lightning Conductor

  3. 简要题意：给定一个长度为 $n$ 的序列 $a_i$ 和一个整数 $k$，现在需要将这个序列划分成 $k$ 个连续段，每个连续段的费用是其中相同元素的对数，求最小费用的和

    $n\le 10^5,k\le 20$

    简要题解：容易得到 $dp$ 方程，$f_{i,k}=min\{f_{j,k-1}+c_{j+1,i}\}$

    其中 $c_{j+1,i}$ 表示将 $[j+1,i]$ 分成一段的费用，能够发现转移方程满足决策单调性

    因为 $c_{x,y}$ 没法 $O(1)$ 求，这里我们只能使用分治法，$c_{j+1,i}$ 的维护使用类似莫队的方法

    时间复杂度 $O(kn\log n)$

    CF 868F Yet Another Minimization Problem

  4. 简要题意：给定一个长度为 $n$ 的序列 $h_i$，求最大的数对 $(i,j),i<j$，其中 $(h_i+h_j)\times (j-i)$ 最大

    $n\le 10^6$

    简要题解：显然对于 $h_i$ 我们只会选择前缀最大值，对于 $h_j$ 我们只会选择后缀最大值，我们考虑对于每个 $h_j$ 求最大的 $h_i$，同时我们猜测这东西有决策单调性，所以我们用分治的做法即可解决问题

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

    不过为了严谨我们还是来证明一下

    不妨设 $i$ 的决策点为 $j$，那么 $\forall k<j,(a_i+a_j)(i-j)\ge (a_i+a_k)(i-k)$

    我们考虑 $i+1$ 的决策点，如果满足决策单调性，那么一定有 $\forall k<j,(a_{i+1}+a_j)(i-j)\ge (a_{i+1}+a_k)(i-k)$

    我们考虑这个式子相当于 $i$ 的式子有什么改变

    能够得到不等式两边的增量为 $(a_{i+1}-a_i)(i-j)+a_{i+1}$ 和 $(a_{i+1}-a_i)(i-k)+a_{i+1}$

    由于 $a_{i+1}<a_i$，所以右边的增量小，所以该不等式依然满足

    2020-2021 ACM-ICPC, Asia Seoul Regional Contest L Two Buildings

  5. 简要题意：给定两个长度为 $n$ 的序列 $a_i$ 和 $b_i$，令 $s_i$ 表示 $b$ 中前 $i$ 大的数字之和，要求 $c_i=\max(a_j+s_{i-j}),j<i$

    $n\le 10^5$

    简要题解：我们不妨将求 $c_i$ 的过程看成一个 $dp$，同时用 $f_i$ 代替 $c_i$

    然后我们发现 $f$ 的决策点是具有单调性的，因为 $s$ 的增量是越来越小的

    然后我们选择单调队列二分还是直接分治都行

    校内赛 合并数组

  6. 简要题意：现在有 $q$ 次询问，每次询问给定 $n$ 和 $k$，求将 $[1,n]$ 这个序列分成 $k$ 段的最小代价和，$[l,r]$ 的代价为 $c(l,r)=\sum_{i=l}^r\sum_{j=i}^r[(i,j)\ge l]$

    $k\le n\le 10^5,q\le 3\times 10^5$

    简要题解：容易发现当 $2^k>n$ 时，答案一定为 $n$，那么我们的 $k$ 就缩小到了 $O(\log n)$ 的级别，我们考虑 $dp$，令 $f_{i,j}$ 表示前 $i$ 个数，分成了 $j$ 段，那么 $f_{i,j}=\min(f_{k,j-1}+c(k+1,i)),k<i$，容易发现转移满足决策单调性，但是 $c(l,r)$ 看起来不是很好求，我们先化简一下 $c(l,r)$，可以得到 $c(l,r)=\sum_{i=l}^rS(\lfloor\frac{r}{i}\rfloor)$，其中 $S(n)=\sum_{i=1}^n\varphi(i)$，我们考虑还是用类似莫队的方法维护 $c(l,r)$，$l$ 移动的时候代价是 $O(1)$ 的，$r$ 移动的时候，所有 $i\ge l,\lfloor\frac{r}{i}\rfloor<\lfloor\frac{r+1}{i}\rfloor$ 的 $i$ 的贡献要改变，容易发现这样的 $i$ 是 $r+1$ 的约数，那么右端点的总移动是 $O(n\log n\ln n)$，我们直接暴力维护这个东西，总的时间复杂度为 $O(n\log^2n\ln n)$，常数非常小，对于每个右端点预处理左端点的答案可以做到 $O(n\log^2 n+n\sqrt n)$

    CF 1603D Artistic Partition

斜率优化

斜率优化适用于 $1D/1D$​ 动态规划

考虑这样一种转移：$f_i=min(f_j+a_i\times c_j+b_i)$，其中 $j<i$

我们将原式展开：$f_i+b_i-a_i\times c_i=f_j$

我们把上式看成直线解析式，$b=f_i+b_i,k=a_i,x=c_j,y=f_j$

对于这条直线，我们知道斜率 $k$，并且知道所有点 $(c_j,f_j)$​，求截距最小，那么相当于把这个直线从最下面向上移动，碰到第一个点停止，此时截距就是我们想要的值

考虑维护这个东西，不妨假设斜率 $k>0$​，那么显然碰到的点都在这些点组成的下凸壳上，我们知道下凸壳的相邻两点组成的直线的斜率是递增的，并且这条直线在上移的时候最先碰到的点是下凸壳上第一个满足 $slope(p_j,p_{j+1})>a_i$ 的点

所以如果这个时候直线的斜率是递增的，我们可以使用单调队列来维护

适用情况

最大值：

需要维护上凸壳，斜率要求为负

斜率 $k$ 递减，每次增加的点的横坐标 $x$ 递增，可以使用单调队列维护

最小值：

需要维护下凸壳，斜率要求为正

斜率 $k$ 和每次增加的点的横坐标 $x$​ 都递增可以使用单调队列维护

其它情况直接上 $cdq$ 吧

模板

下凸壳

1
2
3
4
5
6
// k 为正, k 和 x 递增
for (int i = 1; i <= n; ++i) { 
    while (h < t && slope(Q[h], Q[h + 1]) < k[i]) ++h;
	while (h < t && slope(Q[t - 1], Q[t]) > slope(Q[t - 1], i)) --t;
    Q[++t] = i; 
}

上凸壳

1
2
3
4
5
6
// k 为正, k 递降, x 递增
for (int i = 1; i <= n; ++i) { 
    while (h < t && slope(Q[h], Q[h + 1]) > k[i]) ++h;
	while (h < t && slope(Q[t - 1], Q[t]) < slope(Q[t - 1], i)) --t;
    Q[++t] = i;
}

例题

  1. 简要题意：给定一个长度为 $n$ 的序列 $a$ 和 $L$，现在需要将序列分成若干段，如果将 $a_i$ 到 $a_j$ 放到一段，那么它们的代价是 $(j-i+\sum_{k=i}^ja_k-L)^2$，求最小代价

    $n\le 5\times 10^4$​

    简要题解：容易得到 $dp$ 式子，$f_i=min\lbrace f_j+(s_i-s_j+i-j-1-L)^2\rbrace$

    我们令 $a_i=s_i+i$，$b_j=s_j+L+1$，那么 $f_i=min\lbrace f_j+(a_i-b_j)^2\rbrace$

    化简成直线的形式可以得到 $f_i-a^2_i+2a_ib_j=f_j+b_j^2$，其中 $y=f_j+b^2_j,x=b_j,k=2a_i,b=f_i-a_i^2$

    其中 $k$ 和 $x$ 均递增，且 $k>0$​​，所以可以直接使用单调队列来维护下凸壳

    Luogu P3195 [HNOI2008]玩具装箱(斜率优化)

  2. 简要题意：有 $n$ 根柱子，每根柱子高度为 $h_i$，如果要架桥在 $i$ 和 $j$ 两根柱子间，需要花费 $(h_i-h_j)^2$，同时会拆掉 $i$ 到 $j$ 之间所有其它柱子，拆掉第 $i$ 根柱子的代价是 $w_i$，求连通 $1$ 和 $n$ 的最小代价，需要注意任意两座桥不能相交除了端点之外的地方相交

    $n\le 10^5,0\le h_i,|w_i|\le 10^6$​

    简要题解：

    容易得到 $dp$ 方程，$f_i=min\lbrace f_j+(h_i-h_j)^2+s_{i-1}-s_j\rbrace $​

    化成直线的形式，$f_i-s_{i-1}-h_i^2+2h_ih_j=f_j+h_j^2-s_j$​，其中 $y=f_j+h_j^2-s_j,x=h_j,k=2h_i,b=f_i-s_{i-1}-h_i^2$

    注意到 $k>0$，但 $k$ 和 $x$ 都不递增，所以只能使用 $cdq$ 来维护下凸壳进行更新

    注意到 $k$ 和 $x$ 是同一个数组，所以 $cdq$ 可以做到 $O(n\log n)$

    Luogu P4655 [CEOI2017]Building Bridges