动态规划

本题单只包含难点在于动态规划的题，不考虑把仅仅把动态规划作为工具使用的题。 ## 动态规划的难点 由于动态规划的子类别实在太多，且子类别间的相通度不高，故很难找到对于所有 dp 起效的共性。 个人认为难点可能有以下几类： - 找**相同的子问题**，即设计状态及转移（常见于区间 dp，状压 dp） - 找**对答案贡献相同的情况**，即压缩状态（常见于计数 dp） - 找问题的某个性质（常见于各种 dp 优化，或看起来跟 dp 八竿子打不着的题） - 调试难度大~~（两行转移有时候就要调半小时）~~ 由于动态规划题常常有极强的技巧性，因此学好动态规划需要题量的积累，和敏锐的直觉。 ## 最优化 DP 和 计数 DP [OI-wiki 动态规划基础](https://oi-wiki.org/dp/basic/) [英文维基](https://en.wikipedia.org/wiki/Dynamic_programming) [OI-wiki 记忆化搜索](https://oi-wiki.org/dp/memo/) 最优化 DP 和 计数 DP 都是不重复计算同样的子问题。 利用记忆化搜索可以更好地理解动态规划。 ## 线性 DP [简单的模型](https://blog.csdn.net/u011815404/article/details/81870275) ## 区间 dp [OI-wiki](https://oi-wiki.org/dp/interval/) P3736，P5336，P9383 ## 树形 dp [OI-wiki](https://oi-wiki.org/dp/tree/) P3349，P5291 ## DAG dp [OI-wiki](https://oi-wiki.org/dp/dag/) [某博客](https://www.cnblogs.com/zhxmdefj/p/11154994.html) 找到拓扑序即可进行 DP。 UVA437，CF721C ## 背包 [OI-wiki](https://oi-wiki.org/dp/knapsack/) [树上背包技巧](https://zhuanlan.zhihu.com/p/316010761) [树上背包技巧进阶](https://www.cnblogs.com/ez-lcw/p/16843245.html) [树上换根背包](https://qoj.ac/problem/4815)，[题解](https://www.cnblogs.com/mekoszc/p/17724858.html) P4516，CF1442D，CF178F3 ## 线段树优化 dp [例题](https://blog.csdn.net/sizeof_you/article/details/83388712) P8476，P6773 ## 可并堆优化 DP P3642 这道题是对于凸函数特殊的处理，使用了[凸包闵可夫斯基和的经典结论](https://www.cnblogs.com/xzyxzy/p/10229921.html)。 ## 分治优化 DP （与“【学习 1】基础优化技巧 1”联动） 特定的分治顺序，如 CDQ 分治，或者点分治，可以用来实现特定顺序的转移。 例如下标大的 DP 值只依赖下标小的 DP 值，可以用 CDQ 分治，先递归左边，再利用左边的信息递归右边。 例如祖先的 DP 值只依赖子树的 DP 值，可以用点分治，先递归分治中心子树的部分，再计算子树的贡献，最后递归计算除了分治中心子树以外其他部分的 DP 值。 ## 状压 dp（含 dp 套 dp） CF1730F，P4590，P8497，P5056 ### 枚举子集等常见操作 熟练 [位运算](https://oi-wiki.org/math/bit) ### 状压 DP [OI-wiki](https://oi-wiki.org/dp/state) [某博客](https://www.cnblogs.com/ljy-endl/p/11627018.html) ### DP 套 DP 其实也是状压 DP，将等价 DP 的结果压成一个状态，在这个状态的基础上进行 DP。 [某学员的博客](https://www.cnblogs.com/dead-X/p/14274671.html) ### 轮廓线优化 [OI-wiki](https://oi-wiki.org/dp/plug/) 实际上就是定义一个合适的转移顺序，一格格地转移。 ## 用矩阵表示 DP 对于计数 DP，如果可以表示成矩阵相乘的形式 $a_{i,j} = \sum_{k=1}^n b_{i, k} c_{k,j}$，那么是有结合律的。 对于最优化 DP，如果可以表示成矩阵相乘的形式 $a_{i, j} = \max_{k=1}^n (b_{i,k} + c_{k,j})$，那么也是有结合律的。 此类问题利用的正是结合律，也就是带结合律的信息都可以用类似方法处理。 ### 快速幂优化 [OI-wiki](https://oi-wiki.org/math/quick-pow/#_7) ### 数据结构优化 此时是使用数据结构维护矩阵乘法了。 #### 序列数据结构 [某博客](https://www.cnblogs.com/luckyblock/p/12127669.html) #### 树上数据结构 此类问题是序列问题的加强版。 [OI-wiki](https://oi-wiki.org/dp/dynamic/) 使用树剖因为涉及单点修改，区间查询，所以复杂度要两个 $\log$。 使用 LCT、[全局平衡二叉树](https://blog.csdn.net/qq_35950004/article/details/88861054)等数据结构可以做到单个 $\log$。 ### 动态 dp 感觉应该被塞进【数据结构】部分（很适合练习代码能力） P5281，P3781 ## 凸优化（wqs 二分） [某博客](https://www.luogu.com.cn/blog/daniu/wqs-er-fen) [可推广至二维的另类 wqs（推销我的博客）](https://www.luogu.com.cn/blog/skc/improved-wqs-er-fen) CF739E，P4383 ## 决策单调性优化 [随便找了一个 dp 优化的博客](https://www.cnblogs.com/flashhu/p/9480669.html) P1880，P3515，P1912，P6246 ### 四边形不等式 [OI-wiki](https://oi-wiki.org/dp/opt/quadrangle/) 对于满足四边形不等式的1D1D型动态规划，其 DP 值具有凸性。[某博客](https://www.cnblogs.com/Itst/p/12805678.html) ### 决策单调性的几种优化方法 #### 分治法（与“【学习 1】基础优化技巧 1”联动） 同样见前期2里的分治转移斜率优化。 #### 半在线的问题的转移方法 一般的问题是 $f$ 转移到 $g$，也就是 $f$ 已经给定，来计算 $g$。 但是半在线的情况就是下标小的 $f$ 转移到下标大的 $f$，这时候分治已经不能满足了。 此时使用单调栈，[见数据分块鸡的子任务四](https://vfleaking.blog.uoj.ac/blog/2292)。 具体的想法就是由于决策点单调，那么每个点作为转移点贡献到的区间也是单调的。在做第 $i$ 个点的转移时，只有前 $i - 1$ 个点有贡献。计算完 $i$ 后需要插入 $i$，此时影响的只有后缀部分的区间，于是使用单调栈可以解决。 细节如下： 如果知道了每个点贡献到的区间，那么转移的时候直接就能知道转移点。 在插入新的点的时候，只需要在后缀上二分出自己的贡献区间（二分到一个点的时候，只需要和这处原来的点作为转移点时，得到的 DP 值进行比较，即可知道自己的贡献区间是否包含这个点）。 #### 线性的转移方法 难度较高且 OI 题中不太用的到。 [SMAWK 算法](https://en.wikipedia.org/wiki/SMAWK_algorithm) 可以查看 2017 年论文集中的冯哲的《浅谈决策单调性动态规划的线性解法》。 半在线的转移也可以使用这个算法的变种。 ## 斜率优化及凸包 P2120，P6302，P4027 ### 斜率优化 [OI-wiki](https://oi-wiki.org/dp/opt/slope/) #### 斜率优化的通用技巧 本质上是处理点积最大化的问题。也就是给定点 $(a, b)$，从点集中选出点 $(c,d)$，最大化 $ac + bd$。 考虑几何意义，答案一定在[凸包](https://oi-wiki.org/geometry/convex-hull/)上（当然这个证明不够严谨）。于是变成了一个计算几何的问题。 于是根据插入点的位置和查询点的位置有很多变式。 插入任意点的问题，维护凸壳的时候需要使用平衡树二分需要删去的段并且完成插入操作。[动态凸包](https://blog.csdn.net/qq_40482358/article/details/88253941) 查询任意点的问题，需要判断点所在的象限以决定使用上凸壳还是下凸壳。同时利用点积的凸性，在凸壳上二分点积点积最大的点。 一般良心的题目，会有插入横坐标单调的情况，这个时候就只需要维护单调栈即可。 一般良心的题目，在插入点横坐标单调甚至先插入所有的点再查询时，还会保证查询点斜率单调（要注意象限问题）。这个时候维护一个指针扫一下即可（需要注意点的删除对指针位置的影响）。 而所谓的单调队列维护斜率优化，使用一个指针加单调栈也是可以的。 ## 单调队列优化 CF797F，AT_arc081_d，CF1131G ### 单调栈/单调队列优化 [OI-wiki](https://oi-wiki.org/dp/opt/monotonous-queue-stack/) 这两个数据结构是很多带单调性或者凸性题目的基础。 ## 生成函数优化 DP ### 卷积形式转移 如果转移中出现了卷积的形式，可以使用支持快速卷积的算法来快速转移（例如一般题目下的 FFT）。 ### 表示成生成函数 如果用生成函数的某项系数 $[z^k]f(z)$ 可以代表 DP $g_k = [z^k]f(z)$，且生成函数的加法乘法等操作可以对应到 DP 的转移上时，可以先用生成函数推式子再得到答案。 见 [OI-wiki 的生成函数专题](https://oi-wiki.org/math/gen-func/intro/)。 ### 计数型背包上的应用 $x^b$ 可以代表体积为 $k$ 的物品，而 $x^k$ 的系数可以代表方案数。 如果有权值为 $a$，体积为 $b$ 的物品，此时乘上 $(1 + ax^b)$ 相当于对这个物品做 01 背包，乘上 $\frac{1}{1 - ax^b}$ 相当于对这个物品做完全背包。 于是如果要删除一个 01 背包的物品，就只需要加入权值为相反数，体积相同的完全背包的物品。 删除完全背包物品的方法类似。 而做 01 背包和做完全背包的方法相信选手都熟能生巧了，于是就能快速地删物品了！ ## 概率与期望 dp [OI-wiki](https://oi-wiki.org/dp/probability/) P2081，CF865C，CF1267G ## 数位 dp [OI-wiki](https://oi-wiki.org/dp/number/) 根据数字比较大小的方式，数位 DP 一般有从低位到高位比较和高位到低位比较两种写法。 CF1194G，P2481 ## NOI 考过的一些 dp 题 P7740，P5472，P6772，P2150 ## 联合省选考过的 dp P6622，P5289，P7519，P4365 ## 其他杂题 P5772，AT_agc001_e，P8321