【动态规划】普及~省选的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+换根

题目列表