【动态规划】普及~省选的dp题
题单介绍
[之前的题单](https://www.luogu.com.cn/paste/k45854e7)
### 0x0 change log
+ 题单于 2020-7-2 重构完成，分成版块并添加了新的题目
+ 如有其余好的dp题欢迎私信我，如有错误欢迎指出
+ 题单的题目列表请以题单描述中的题目为准，新版题单中的题目列表还没有更新
+ 2020-7-4 加入了树形dp综合练习题，其他版块新增 2 道题
+ 2020-7-12 更新了「分治法」版块，撤下了题目编排中的题；由于题目数量限制后面会以每个版块单独的题单呈现
+ 2020-7-16 子题单施工完毕，已经添加链接
+ 2020-8-23 更新了「状压dp」「区间dp」，加入了「长链剖分」
+ 2020-10-21 加入了一些题目，新增「子集dp」「数据结构优化dp」「缩点」
本题单共 96 题
### 0x1 暴力dp
别考虑优化，推出方程直接AC
这部分的子题单：[「0x1 暴力dp」](https://www.luogu.com.cn/training/13993)
#### 0x10 线性dp
大多思维难度不高，也不需要啥优化，是基础的dp练手题
[P1095 守望者的逃离](https://www.luogu.com.cn/problem/P1095) 普通的线性dp，简单的分类讨论就好了
[P1077 摆花](https://www.luogu.com.cn/problem/P1077) 计数类dp，甚至不需要分类讨论
[P3842 [TJOI2007]线段](https://www.luogu.com.cn/problem/P3842) 线性dp，不过是要分类讨论
[P1541 乌龟棋](https://www.luogu.com.cn/problem/P1541) 暴力dp，很裸的题
[P4059 [Code+#1]找爸爸](https://www.luogu.com.cn/problem/P4059) 暴力dp，按照末尾空格分类
---
#### 0x11 背包问题
题目中大多有价值和体积，有些时候也要把题目转化成价值和体积的模型
[P1833 樱花](https://www.luogu.com.cn/problem/P1833) 多重背包模板
[P1064 金明的预算方案](https://www.luogu.com.cn/problem/P1064) 带有附带物品的背包问题，为树上背包打基础
[P1941 飞扬的小鸟](https://www.luogu.com.cn/problem/P1941) 背包建模
[P2340 [USACO03FALL]Cow Exhibition G](https://www.luogu.com.cn/problem/P2340) 巧妙的背包问题&分类讨论
---
#### 0x12 区间dp
状态大多为一个区间
[P1880 [NOI1995]石子合并](https://www.luogu.com.cn/problem/P1880) 简单的区间dp，配合断环成链的技巧就行啦
[P3146 [USACO16OPEN]248 G](https://www.luogu.com.cn/problem/P3146) 和上题类似，也是区间dp
[P1063 能量项链](https://www.luogu.com.cn/problem/P1063) 经典的区间dp
[P4342 [IOI1998]Polygon](https://www.luogu.com.cn/problem/P4342) 区间dp+断环成链
[CF149D Coloring Brackets](https://www.luogu.com.cn/problem/CF149D) 区间dp，特殊的转移方式
[UVA12991 Game Rooms](https://www.luogu.com.cn/problem/UVA12991) 区间 dp 的思想引出正解
---
#### 0x13 状压dp
将状态压缩成一个任意进制的数进行dp，适用于数据范围小的dp
[P3052 [USACO12MAR]Cows in a Skyscraper G](https://www.luogu.com.cn/problem/P3052) 状压dp+枚举状态的子集
[P2704 [NOI2001]炮兵阵地](https://www.luogu.com.cn/problem/P2704) 状压dp+空间优化
[P3959 宝藏](https://www.luogu.com.cn/problem/P3959) 状压dp，按层转移
[P2150 [NOI2015]寿司晚宴](https://www.luogu.com.cn/problem/P2150) 隐藏的数据范围
[P2566 [SCOI2009]围豆豆](https://www.luogu.com.cn/problem/P2566) 状压dp+计算几何技巧
---
棋盘上还有按格转移的状压dp，可以节省一点时间复杂度，代码量较大
[P3272 [SCOI2011]地板](https://www.luogu.com.cn/problem/P3272) 插头dp入门题
[P3190 [HNOI2007]神奇游乐园](https://www.luogu.com.cn/problem/P3190) 也是插头dp入门题
[P5056 【模板】插头dp](https://www.luogu.com.cn/problem/P5056) 哈密尔顿回路，比较困难的插头dp
[P4262 [Code+#3]白金元首与莫斯科](https://www.luogu.com.cn/problem/P4262) 带有技巧性的插头/轮廓线dp
[P2337 [SCOI2012]喵星人的入侵](https://www.luogu.com.cn/problem/P2337) 复杂的插头dp
---
#### 0x14 数位dp
对于数进行dp
[P2657 [SCOI2009]windy数](https://www.luogu.com.cn/problem/P2657)
[P4124 [CQOI2016]手机号码](https://www.luogu.com.cn/problem/P4124)
[P2602 [ZJOI2010]数字计数](https://www.luogu.com.cn/problem/P2602)
↑都是数位dp入门题↑
[P2481 [SDOI2010]代码拍卖会](https://www.luogu.com.cn/problem/P2481) 带有技巧性的数位dp
---
### 0x2 树形dp
NOIp/csp 常考类型，最重要的dp
这部分的子题单：[「0x2 树形dp」](https://www.luogu.com.cn/training/13994)
#### 0x20 基础的树dp
没什么难度，入门级别的题目
[P1352 没有上司的舞会](https://www.luogu.com.cn/problem/P1352) 最大权独立集问题
[P2016 战略游戏](https://www.luogu.com.cn/problem/P2016) 最小权覆盖集问题
---
#### 0x21 树上背包
有依赖性的背包
[P2014 [CTSC1997]选课](https://www.luogu.com.cn/problem/P2014) 树上背包模板
[P1273 有线电视网](https://www.luogu.com.cn/problem/P1273) 树上背包经典题
[P1272 重建道路](https://www.luogu.com.cn/problem/P1272) 类似树上背包的树形dp
[P3354 [IOI2005]Riv 河流](https://www.luogu.com.cn/problem/P3354) 树上背包，也有更快的wqs二分做法
---
#### 0x22 二次扫描法
也叫换根dp，一般第一次扫描考虑子树内的贡献，第二次扫描考虑子树外/全局的贡献
[P3478 [POI2008]STA-Station](https://www.luogu.com.cn/problem/P3478) 换根dp模板题
[P2986 [USACO10MAR]Great Cow Gathering G](https://www.luogu.com.cn/problem/P2986) 换根dp模板题
[P3047 [USACO12FEB]Nearby Cows G](https://www.luogu.com.cn/problem/P3047) 换根dp，也有其他的方法
[CF708C Centroids](https://www.luogu.com.cn/problem/CF708C) 换根dp好题
[P6419 [COCI 2015]Kamp](https://www.luogu.com.cn/problem/P6419) 分类讨论较麻烦的换根dp（听说被lswn分类3种吊打了/youl）
[P3647 [APIO2014]连珠线](https://www.luogu.com.cn/problem/P3647) 比较困难的换根dp
---
#### 0x23 基环树
$n$ 条边 $n$ 个点，突破口就在环上
[P1453 城市环路](https://www.luogu.com.cn/problem/P1453) 基环树上最大权独立集问题
[P4381 [IOI2008]Island](https://www.luogu.com.cn/problem/P4381) 基环树直径问题
---
#### 0x24 虚树
多次询问询问，总点数不多时可以去掉一些无用的点把时间复杂度优化到 $\Theta(n\log n)$
[P2495 [SDOI2011]消耗战](https://www.luogu.com.cn/problem/P2495) 虚树dp模板题
[P3233 [HNOI2014]世界树](https://www.luogu.com.cn/problem/P3233) 虚树dp比较难的题
---
#### 0x25 长链剖分
当 dp 状态只和深度有关的时候可以通过长链剖分优化到均摊 $\Theta (1)$ 的复杂度
[CF1009F Dominant Indices](https://www.luogu.com.cn/problem/CF1009F) 长链剖分模板
[P5904 [POI2014]HOT-Hotels 加强版](https://www.luogu.com.cn/problem/P5904) 神仙 dp+长链剖分优化
[P4292 [WC2010]重建计划](https://www.luogu.com.cn/problem/P4292) 01 分数规划+线段树维护长链剖分
---
#### 0x26 树形dp综合练习-part1
比较简单基础的题
[P3174 [HAOI2009]毛毛虫](https://www.luogu.com.cn/problem/P3174)
[P3554 [POI2013]LUK-Triumphal arch](https://www.luogu.com.cn/problem/P3554)
[CF219D Choosing Capital for Treeland](https://www.luogu.com.cn/problem/CF219D)
[P1131 [ZJOI2007]时态同步](https://www.luogu.com.cn/problem/P1131)
[P2052 [NOI2011]道路修建](https://www.luogu.com.cn/problem/P2052)
[P5658 括号树](https://www.luogu.com.cn/problem/P5658)
---
#### 0x27 树形dp综合练习-part2
稍微难一点的树dp
[P4253 [SCOI2015]小凸玩密室](https://www.luogu.com.cn/problem/P4253)
[P4516 [JSOI2018]潜入行动](https://www.luogu.com.cn/problem/P4516)
[CF512D Fox And Travelling](https://www.luogu.com.cn/problem/CF512D)
[CF543D Road Improvement](https://www.luogu.com.cn/problem/CF543D)
[CF1146F Leaf Partition](https://www.luogu.com.cn/problem/CF1146F)
[CF1016F Road Projects](https://www.luogu.com.cn/problem/CF1016F)
[CF671D Roads in Yusland](https://www.luogu.com.cn/problem/CF671D)
---
### 0x3 dp 优化
有些时候暴力 dp 不再适用了，于是需要一些优化
这部分的子题单：[「0x3 dp优化」](https://www.luogu.com.cn/training/14005)
#### 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) 缩点+树上背包
---
### 0x4 数学问题
数论、期望+dp
这部分的子题单：[「0x4 数学问题」](https://www.luogu.com.cn/training/14006)
#### 0x40 数论dp
说数论其实也就是一个质数
[P6280 [USACO20OPEN]Exercise G](https://www.luogu.com.cn/problem/P6280) 数论+dp
---
#### 0x41 期望dp
数学期望的递推
[P1365 WJMZBMR打osu! / Easy](https://www.luogu.com.cn/problem/P1365)
[P1654 OSU!](https://www.luogu.com.cn/problem/P1654) 这两题均为 combo 的问题
[P1850 换教室](https://www.luogu.com.cn/problem/P1850) 期望dp&floyd
[P4284 [SHOI2014]概率充电器](https://www.luogu.com.cn/problem/P4284) 期望dp+换根