序言
DP问题算是OI里经常出现的一类问题。
该类问题是OI中独有的，这种问题的思考方式在我看来并不同于其他学科。是一种独立的方向，这些算法其中体现了很多美感。
DP问题分类广泛，题目众多。该篇文章正在尝试逐渐完善。若您在阅读中有任何问题 / 疑惑十分期待您留言提出。
LIS问题
我们从这一个非常经典的问题开始吧。考虑最长上升子序列定义： $A\subset C, \forall x \in \{x | card(A) - 1\}, a_x < a_{x + 1}$ 求 $ _{\max}card(A)$
我们考虑子任务 $f_i$ 为从 $[1, i] \in \mathbb{Z}$ 的最长上升子序列长度。
考虑我们每次如何得到这个长度。
考虑到我们可以每次从前面中任意一个值推到这个点。如果这个值小于当前值，那么可以添加到这个最长上升子序列中。如果每一次都是这么添加，一定可以符合 $LIS$ 的性质。
通过这种做法，得到的时间复杂度是 $O(n^2)$
我们考虑这么一种优化。
权值最多有 $n$ 种，我们可以将其离散化。并在每次找到后记录在对应权值字典的位置上。然后每次找值就是找在权值上 $1$ 到该点（不包含）的最大值，该操作可以使用线段树维护，时间复杂度降至 $O(n \log n)$。
LCS 问题
最长公共子序列。
首先考虑一般情况：
我们不妨定义 $f_{i, j}$ 为第一行考虑到 $i$, 第二行考虑到 $j$ 的情况下，最长公共子序列的长度。
若当前 $a_i = b_j$ 时证明此时成立即可以从 $f_{i-1,j-1}$ 递推而来并对此时答案贡献 $1$。
同时我们发现 $f_{i, j - 1}$ 比任意 $f_{i, [0, j - 1]}$ 都会更优（同理可得 $f_{i-1, j}$ 更优）所以可以从这两个状态下推过来，但对答案并没有贡献。
考虑需要遍历任意点，综合时间复杂度为 $O(n^2)$
洛谷在这题中给出了一个特殊性质：输入数据呈一个 $[1, n]$ 的排列。也就是说两个序列出来的值完全相同。
这个时候我们盯着上一个看，我们考虑如果第一个值匹配后，后面的值有什么限制。
考虑第二个选择的位置所构成的序列必须是单调递增的。所以得出来的限制：
每一次选择后，下一个选择的值在第二个数组中的对应位置要更比这次选择所对应的位置。
即我们可以把第一个数组看成 $1,2,3,...,n$ 的排列。那么可以把第二个数组建立映射关系，那么显然，答案就变为了在第二个数组上求LIS问题。
所以我们直接初始化第一行的点在第二行出现的位置。再用LIS问题求解。综合LIS问题的 $O(n \log n)$ 最终时间复杂度即为 $O(n \log n)$
此时我们重新考虑回一般情况，我们发现这种技巧其实同样适用于一般情况。
但是值得注意的是如果遇到相等的情况下，我们要求最长不下降子序列。
按照上面的写就行。
#include <iostream>
#include <cstdio>
using namespace std;
const int N = 1e5 + 5;
int a[N], b[N], c[N];
struct node {
int l, r;
int ax;
}tr[N * 4];
int pushup(int u) {
tr[u].ax = max(tr[u << 1 | 1].ax, tr[u << 1].ax);
}
void build(int u, int l, int r) {
tr[u].l = l;
tr[u].r = r;
if (l == r) {
tr[u].ax = 0;
return ;
}
int mid = l + r >> 1;
build(u << 1, l, mid);
build(u << 1 | 1, mid + 1, r);
}
int query(int u, int l, int r) {
if (tr[u].l >= l && tr[u].r <= r) {
return tr[u].ax;
}
int mid = tr[u].l + tr[u].r >> 1;
int res = 0;
if (r > mid) {
res = max(res, query(u << 1 | 1, l, r));
}
if (l <= mid) {
res = max(res, query(u << 1, l, r));
}
return res;
}
void add(int u, int l, int v) {
if (tr[u].l == tr[u].r && tr[u].l == l) {
tr[u].ax = v;
return ;
}
int mid = tr[u].l + tr[u].r >> 1;
if (l > mid) {
add(u << 1 | 1, l, v);
} else {
add(u << 1, l, v);
}
pushup(u);
}
int main() {
int n;
cin >> n;
for (int i = 1; i <= n; i ++ ) {
cin >> a[i];
}
for (int i = 1; i <= n; i ++ ) {
cin >> b[i];
c[b[i]] = i;
}
for (int i = 1; i <= n; i ++ ) {
a[i] = c[a[i]];
}
build(1, 1, n);
int res = 0;
for (int i = 1; i <= n; i ++ ) {
int t = query(1, 1, a[i] - 1);
res = max(res, t + 1);
add(1, a[i], t + 1);
}
cout << res << endl;
return 0;
}这是两个比较经典的模型，下面我们大致看一下背包问题。
背包问题
前排提示：
练习题统一在后面，前面先大概讲一遍。
01背包
这又是一个经典的问题。对于每一种物品有体积 $w_i$ 和价值 $v_i$。现在有一个容量为 $n$ 的背包。请问拿那些物品能在容量内拿更多东西。
考虑我们维护 $f_{i, j}$ 为考虑前 $i$ 个物品，拿到体积为 $j$ 的最大价值。
我们发现可以从 $f_{i - 1, j - w_i} + v_i$ 推过来。
我们考虑每一次都只跟上一次有关，可以压掉第一维。
在本题种可以直接删掉第一维，然后倒着找。这样的正确性是因为每次从之前的地方找并且之前的地方还没有被更新过。
但是更一般的情况下，我们还可以考虑滚动数组，即将第一维改成 $0, 1$ 。在一般情况下空间是足够的。
完全背包
考虑完全背包即为每种物品可以拿无限个。
$f_{i - 1, j - w_i * k} + v_i * k$
或者我们考虑其实可以从 $f_{i, j - w_i} + v_i$ 递推过来。但是要注意顺序
同样我们考虑压掉第一维。
然后正序跑一遍即可。
多重背包
多重背包即为每种物品可以拿 $c_{i}$ 个。
考虑上一个的式子，只需要保证 $k \leq c_{i}$
我们把式子写的标准一点：
$$ f_{i, j} = \max_{1\leq k \leq \min(\frac{v}{w_i}, l_i)}(f_{i, j - k * w_i} + k * v_i) $$
那么我们可以考虑完全背包的暴力时间复杂度 $O(n^3)$
我们可以认为这是很难接受的。
我们可以考虑单调队列优化：我们考虑上面的式子
若我们考虑对于每一个 $f_{i, j}$ 的来源。我们会发现是从所有 $j - k*w_i$ 递推而来。
我们发现对于每一个 $j \% w_i$ 相同的数都是由同一段构成的。
我们不妨假设这个值 $t = j \% w_i$ , 那么对于当前的 $f_{i, t + c * w_i}$ 都可以由现在这个 $f$ 值 加上 $c * f_i$ 。
那么我们可以通过这个得到一个式子：
$$ f_{i, t + c * w_i} = \max_{c - l_i \leq k \leq c}(f_{i - 1, t + k * w_i} + (c-k) * w_i) $$
如果我们把这个式子拆开即可得到：
$$ f_{i, t + c * w_i} = \max_{c - l_i \leq k \leq c}(f_{i - 1, t + k * w_i} + c * w_i - k * w_i) $$
$$ f_{i, t + c * w_i} = \max_{c - l_i \leq k \leq c}(f_{i - 1, t + k * w_i} - k * w_i) + c * w_i $$
考虑到每次只需要考虑之前最优的即可，这个式子可以运用单调队列(滚动数组)的思想优化。时间复杂度降至 $O(n^2)$
单调队列优化的具体内容将在后面单独说明。
在这里先说明一下这个式子的必要性：
易得，$c - l_i$ 和 $c$ 在正序遍历时是单调的。并且 $\max$ 的取值只与 $k$ 有关。是单调队列的充要条件。
题目分享
P1504
待补充...
单调队列优化
前置知识
单调队列 模板题：滑动窗口 /【模板】单调队列
算法思路
考虑前面的多重背包的式子并进一步简化成下面的式子：
$$ f_{i, j} = \max_{(l_1)\leq k \leq (l_2)}\{{f_{i - 1, k} + v_a}\} + v_b $$
当且仅当 $j$ 增大时 $l_1$ 呈上升趋势， $l_2$ 呈上升趋势，$v_a$ 与 $j$ 无关。
（而且上面的式子其实并不是最简形式，只是题目通常可以化成这种形式）
我们考虑单调队列维护前面的 $\max$ （当然其实 $\min$ 也行， 同样道理）。
我们发现如果在 $j$ 递增时，如果选择靠前面的值如果小于后面的值。那么这个值在下一个值后再也不可能选中这个值。因为 $l_1， l_2$ 呈上升趋势，相当于后浪（比你小还比你强，那么你永无出头之日）。
算法流程
- 对于一个新的 $j$ ，从最优中剔除不符合条件的。
- 将当前点加入队列。
- 从尾部进入，剔除更不优的（驱赶老年人早日回归whk）
其中考虑 $f_{i, j}$ 的答案的话需要考虑加在哪里 2, 3中间或者1, 2中间（由 $k$ 右边的符号决定）。
优化程度
通常可以降掉一个 $n$ 。
例如：从 $O(n^3)$ -> $O(n^2)$ 。
结尾
本篇文章将会持续更新，该部分内容极多。而且需要大量练习题。
感谢
特别感谢 @Meaninglessness 对本篇文章大量内容的审阅与校对。以及提出本文中大部分内容的建议。
TODO
优化
- [ ] 斜率优化
DP大类
- [ ] 区间DP
- [ ] 状态压缩DP
- [ ] 数位DP
以及每种类型的题目。
2 条评论
一篇高质量的文章！
催更（（