【CSP-S 2021 复习】DP 总结

CSP-S 2021 前写的。

0. 前言

这个是为了复习前面的提高组的知识，所以可能不会复习提高组之外的知识。

没有具体的大纲，~~大纲又没有写清楚~~，所以只能看着办吧。

【8】动态规划的 常用优化

这个是 DP 专题。

1. 大概内容

背包问题的基础以及变式
状态自动机模型
状态压缩 DP
区间 DP
树形 DP
数位 DP
单调队列优化 DP
数据结构优化 DP
倍增优化 DP

2. 每一个的分类以及大体思路

1）背包问题

这个其实是比较简单的。（

看一下这个题：CSP-J 2019 T3

这个题当时我在考场上想了很久， 1h 后才发现有想法。

一个完全背包的好题。

其他题我就不推荐了。

关于代码，其实没有什么好说的，大概就是需要我们发现背包模型的问题。

比如发现 $n$ 个物品，以及有一定的取用的限制而不能全部取得的时候，可以考虑使用背包。

2）状态自动机模型

这个大家可能有一点陌生，其实就是 $f[i][j]$ 表示 $i$ 天并且状态为 $j$ 的某种值。

推荐这个题：AcWIng 1057 股票买卖 IV

分别用 0 表示为已卖出，1 表示手头有股票。

就可以比较简单的转移了.

DP 问题其实比较简洁，所以代码没有什么可以多说的。

当遇到明显是 DP 的时候，但是如果没有状态的话很难转移，那么就可以考虑加上状态一维了。

3）状态压缩 DP

这类题目其实有一个比较明显的特征：个数一般不会超过 15 个。

有以下两题型：

棋盘式（即存下每一行的状态，然后行之间直接转移）
集合式（用二进制压缩每一个元素是否在集合内，按照这个转移）

棋盘式的推荐题：NOI2001

集合式的推荐题：NOIP2016

这两个都非常经典，相信大家都做过。

NOI2001 的题目要压缩两行，然后按照行的方式来转移。

同时，这一个题目需要进行一些优化，比如提前存下来一行内合法的状态。

空间上，需要使用滚动数组实现。

NOIP2016 的题目是一个重复覆盖问题，当然需要一点的计算几何。

这里介绍状态压缩的解法。

需要存下来猪被覆盖的集合，然后每一只小鸟分别转移。

DLX 的解法就不介绍了。

这类题首先注意范围，然后还要注意二进制运算的特殊性，可以优化代码难度及常数。

4）区间 DP

区间 DP 的题目的数据范围一般还是比较小，但是比状态压缩大一些，一般在 30~100 之间，时间复杂度为 $O(n^3)\sim O(n^5)$，而且一般跑不满。

区间 DP 分为两种打法，分别是迭代法和递归法。

迭代法就是一堆 for，而递归法就是 void dp(int x){...dp(i)...} 之类的。

这里大概有一维线性，一维环形，二维等几种情况。

这个就是注意边界问题，还有就是迭代式一定要第一维循环 len，第二维循环头结点，这样才能保证当前状态所用到的状态都是计算过的。

5）树形 DP

这一类 DP 大多都是 $O(n)$ 的算法，可能有一些 $O(n\log n)$ 的东西（比如对子树得到的答案排序之类的）。

这类题目一般都比较麻烦，比如要进行数学推导，将求的东西转化为子树和父节点的信息可以分开维护，然后简单合并。

还有，这种题还需要换根技巧，就是将父亲的答案也合并进入儿子的答案，将儿子作为根。

题目不好找，就这样了吧。

大概有一个这个题：CSP-S2019 T6

（因为我还没做，所以后面在更新

6）数位 DP

这种题目其实都有一定的套路，认真看了我的代码的同学应该都有印象。

int dp(int n)
{
    if (!n) return /*0 / 1*/;
    vector <int> nums;
    while (n) nums.push_back(n % 10), n /= 10;
    for (int i = nums.size() - 1; ~i; -- i)
    {
        int &x = nums[i];
        for (int j = 0; j < x; ++ j) /*do with j*/;
    }
}

就是这样一个套路，也没有多么难。

推荐一个题：LOJ 10168 恨 7 不成妻

7）各种优化

核心思想就是 排除无用状态。

a. 单调队列

这个就是一个简单的道理：如果 a 比 b 差，但是 a 会比 b 先弹出决策选择区（就是 a 可选的时候 b 都可以选），那么 a 就永远没有用。

比如说这个题：CSP-S2019 T5

这个题就是一个典型的单调队列优化 DP ~~（外带卡时空~~

这个的转移方程大概是这样：

$f_i=\max_{suf_j\leq s_i-s_j}(f_j+(s_i-s_j)^2)$ $suf_i=s_i-s_j$

其中，$suf_i$ 中用到的 $j$ 是 $f_i$ 转移用到的 $j$，表示最后一段的长度。

首先，很明显 $j$ 越靠后答案一定更优，因为最后一段越小，肯定限制就越小，分的段数就越多，答案就越小。

但是，转移的条件是 $suf_j+s_j\leq s_i$。

所以如果 $suf_j+s_j\geq suf_k+s_k$ 并且 $j<k$，那么 $j$ 就没有用了。

代码大概就长这样：

for (int i = 1; i <= n; ++ i)
{
    while (hh < tt && a[q[hh + 1]] + suf[q[hh + 1]] <= a[i])//breakpoint
        hh ++;
    f[i] = f[q[hh]] + (B)(a[i] - a[q[hh]]) * (a[i] - a[q[hh]]);
    suf[i] = a[i] - a[q[hh]];
    while (hh < tt && a[q[tt]] + suf[q[tt]] > a[i] + suf[i]) tt --;
    q[++ tt] = i;
}

其中，breakpoint 所代表的意思，就是要找到最后一个满足 $suf_j+s_j\leq s_i$ （往后越优）。

b. 数据结构优化

这个最简单的应用就是这个：

给出 $n$ 点的位置 $(x_i,y_i)$，每一个点只能向右上方（包含边界）连有向边，求最长的路径。

这个首先离散化，不是重点，跳过了。

然后按照 $x$ 的位置倒序枚举，然后对于一个点 $(x_i,y_i)$，前面枚举到的点都 $x_j\geq x_i$，所以我们要在枚举过的点中找到 $y_j\leq y_i$ 中 $f_j$ 的最大值。

这个可以使用线段树维护，以 $y$ 坐标作为 build(1, 1, n) 的，维护 $f_i$ 的最大值，询问时直接 query(1, y[j], n) 就可以了。

c. 倍增优化

这个是一个经典的问题：NOIP2012 提高组

（虽然经典，可我还是没有过

所以略过了。