0x3 dp优化

[这个题单](https://www.luogu.com.cn/training/1435)的子题单 ### 0x3 dp 优化 有些时候暴力 dp 不再适用了，于是需要一些优化 #### 0x30 单调队列优化 「一个人要是比你小，还比你强，那你就永远打不过他了」——单调队列 [P2627 [USACO11OPEN]Mowing the Lawn G](https://www.luogu.com.cn/problem/P2627) [P2569 [SCOI2010]股票交易](https://luogu.com.cn/problem/P2569) 都比较模板，一般看完转移方程就能看出单调队列的影子 [CF939F Cutlet](https://www.luogu.com.cn/problem/CF939F) 比较难的单调队列 dp --- #### 0x31 决策单调性优化 当一个转移方程中的价值函数满足四边形不等式时，那么这个方程的决策单调不降，这时就可以用二分+队列来维护 [P1912 [NOI2009]诗人小G](https://luogu.com.cn/problem/P1912) 决策单调性优化模板题 --- #### 0x32 斜率优化 数形结合，适用于 $f_i=\min\{-kx+y\}$ 形式的方程，用单调队列维护一个凸壳，降低复杂度 [P3195 [HNOI2008]玩具装箱](https://www.luogu.com.cn/problem/P3195) [P4360 [CEOI2004]锯木厂选址](https://www.luogu.com.cn/problem/P4360) [P3628 [APIO2010]特别行动队](https://www.luogu.com.cn/problem/P3628) [CF311B Cats Transport](https://www.luogu.com.cn/problem/CF311B) ↑都是模板题↑ --- #### 0x33 分治法 用线段树分治和cdq分治的思想来优化 [P4095 [HEOI2013]Eden 的新背包问题](https://www.luogu.com.cn/problem/P4095) 线段树分治+背包 [P3120 [USACO15FEB]Cow Hopscotch G](https://www.luogu.com.cn/problem/P3120) 类cdq分治 --- #### 0x34 凸优化dp wqs二分，给每个物品设置一个代价，从而找到最优解；但是注意函数必须满足凸性 [CF739E Gosha is hunting](https://www.luogu.com.cn/problem/CF739E) wqs二分模板题 [P4767 [IOI2000]邮局](https://www.luogu.com.cn/problem/P4767) wqs二分+决策单调性优化 --- #### 0x35 矩阵加速dp 利用有结合律的矩阵乘法优化，当然矩阵乘法可以是广义的 [P2579 [ZJOI2005]沼泽鳄鱼](https://www.luogu.com.cn/problem/P2579) 矩阵快速幂+周期 [P3216 [HNOI2011]数学作业](https://www.luogu.com.cn/problem/P3216) 分段矩阵快速幂 [P2886 [USACO07NOV]Cow Relays G](https://www.luogu.com.cn/problem/P2886) 矩阵加速floyd [P3502 [POI2010]CHO-Hamsters](https://www.luogu.com.cn/problem/P3502) 广义矩阵快速幂 --- #### 0x36 动态dp 数据结构优化资瓷修改的dp [P4719 【模板】"动态 DP"&动态树分治](https://www.luogu.com.cn/problem/P4719) 动态树上最大权独立集问题 [P5024 保卫王国](https://www.luogu.com.cn/problem/P5024) 动态树上最小权覆盖集问题 --- #### 0x37 容斥原理 利用容斥优化dp [P5664 Emiya 家今天的饭](https://www.luogu.com.cn/problem/P5664) 剪去无用状态+补集转化 [P3349 [ZJOI2016]小星星](https://www.luogu.com.cn/problem/P3349) 容斥+树形dp [CF348D Turtles](https://www.luogu.com.cn/problem/CF348D) 不相交路径的经典问题 --- #### 0x38 子集 dp 又称 sos dp，利用一种方法将子集求和的复杂度从 $\Theta(3^n)$ 降到 $\Theta(2^nn)$ [CF449D Jzzhu and Numbers](https://www.luogu.com.cn/problem/CF449D) [P6442 [COCI2011-2012#6] KOŠARE](https://www.luogu.com.cn/problem/P6442) [CF383E Vowels](https://www.luogu.com.cn/problem/CF383E) 均为容斥+sos dp --- #### 0x39 数据结构优化 dp 大多为线段树或者树状数组来优化 dp [P2605 [ZJOI2010]基站选址](https://www.luogu.com.cn/problem/P2605) 线段树优化 [P3287 [SCOI2014]方伯伯的玉米田](https://www.luogu.com.cn/problem/P3287) 二维树状数组优化 --- #### 0x3A 缩点 将双联通/强连通分量缩点再按拓扑序进行dp [P2656 采蘑菇](https://www.luogu.com.cn/problem/P2656) 缩点 dp [P2515 [HAOI2010]软件安装](https://www.luogu.com.cn/problem/P2515) 缩点+树上背包