- BC20260025's blog
DP题单（洛谷转）
-
BC20260025
LV 6
@
2023-12-31 22:43:58
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」
0x10 线性dp
大多思维难度不高，也不需要啥优化，是基础的dp练手题
P1095 守望者的逃离 普通的线性dp，简单的分类讨论就好了
P1077 摆花 计数类dp，甚至不需要分类讨论
P3842 [TJOI2007]线段 线性dp，不过是要分类讨论
P1541 乌龟棋 暴力dp，很裸的题
P4059 [Code+#1]找爸爸 暴力dp，按照末尾空格分类
0x11 背包问题
题目中大多有价值和体积，有些时候也要把题目转化成价值和体积的模型
P1833 樱花 多重背包模板
P1064 金明的预算方案 带有附带物品的背包问题，为树上背包打基础
P1941 飞扬的小鸟 背包建模
P2340 [USACO03FALL]Cow Exhibition G 巧妙的背包问题&分类讨论
0x12 区间dp
状态大多为一个区间
P1880 [NOI1995]石子合并 简单的区间dp，配合断环成链的技巧就行啦
P3146 [USACO16OPEN]248 G 和上题类似，也是区间dp
P1063 能量项链 经典的区间dp
P4342 [IOI1998]Polygon 区间dp+断环成链
CF149D Coloring Brackets 区间dp，特殊的转移方式
UVA12991 Game Rooms 区间 dp 的思想引出正解
0x13 状压dp
将状态压缩成一个任意进制的数进行dp，适用于数据范围小的dp
P3052 [USACO12MAR]Cows in a Skyscraper G 状压dp+枚举状态的子集
P2704 [NOI2001]炮兵阵地 状压dp+空间优化
P3959 宝藏 状压dp，按层转移
P2150 [NOI2015]寿司晚宴 隐藏的数据范围
P2566 [SCOI2009]围豆豆 状压dp+计算几何技巧
棋盘上还有按格转移的状压dp，可以节省一点时间复杂度，代码量较大
P3272 [SCOI2011]地板 插头dp入门题
P3190 [HNOI2007]神奇游乐园 也是插头dp入门题
P5056 【模板】插头dp 哈密尔顿回路，比较困难的插头dp
P4262 [Code+#3]白金元首与莫斯科 带有技巧性的插头/轮廓线dp
P2337 [SCOI2012]喵星人的入侵 复杂的插头dp
0x14 数位dp
对于数进行dp
↑都是数位dp入门题↑
P2481 [SDOI2010]代码拍卖会 带有技巧性的数位dp
0x2 树形dp
NOIp/csp 常考类型，最重要的dp
这部分的子题单：「0x2 树形dp」
0x20 基础的树dp
没什么难度，入门级别的题目
P1352 没有上司的舞会 最大权独立集问题
P2016 战略游戏 最小权覆盖集问题
0x21 树上背包
有依赖性的背包
P2014 [CTSC1997]选课 树上背包模板
P1273 有线电视网 树上背包经典题
P1272 重建道路 类似树上背包的树形dp
P3354 [IOI2005]Riv 河流 树上背包，也有更快的wqs二分做法
0x22 二次扫描法
也叫换根dp，一般第一次扫描考虑子树内的贡献，第二次扫描考虑子树外/全局的贡献
P3478 [POI2008]STA-Station 换根dp模板题
P2986 [USACO10MAR]Great Cow Gathering G 换根dp模板题
P3047 [USACO12FEB]Nearby Cows G 换根dp，也有其他的方法
CF708C Centroids 换根dp好题
P6419 [COCI 2015]Kamp 分类讨论较麻烦的换根dp（听说被lswn分类3种吊打了/youl）
P3647 [APIO2014]连珠线 比较困难的换根dp
0x23 基环树
条边 个点，突破口就在环上
P1453 城市环路 基环树上最大权独立集问题
P4381 [IOI2008]Island 基环树直径问题
0x24 虚树
多次询问询问，总点数不多时可以去掉一些无用的点把时间复杂度优化到
P2495 [SDOI2011]消耗战 虚树dp模板题
P3233 [HNOI2014]世界树 虚树dp比较难的题
0x25 长链剖分
当 dp 状态只和深度有关的时候可以通过长链剖分优化到均摊 的复杂度
CF1009F Dominant Indices 长链剖分模板
P5904 [POI2014]HOT-Hotels 加强版 神仙 dp+长链剖分优化
P4292 [WC2010]重建计划 01 分数规划+线段树维护长链剖分
0x26 树形dp综合练习-part1
比较简单基础的题
P3554 [POI2013]LUK-Triumphal arch
CF219D Choosing Capital for Treeland
0x27 树形dp综合练习-part2
稍微难一点的树dp
0x3 dp 优化
有些时候暴力 dp 不再适用了，于是需要一些优化
这部分的子题单：「0x3 dp优化」
0x30 单调队列优化
「一个人要是比你小，还比你强，那你就永远打不过他了」——单调队列
P2627 [USACO11OPEN]Mowing the Lawn G
P2569 [SCOI2010]股票交易 都比较模板，一般看完转移方程就能看出单调队列的影子
CF939F Cutlet 比较难的单调队列 dp
0x31 决策单调性优化
当一个转移方程中的价值函数满足四边形不等式时，那么这个方程的决策单调不降，这时就可以用二分+队列来维护
P1912 [NOI2009]诗人小G 决策单调性优化模板题
0x32 斜率优化
数形结合，适用于 形式的方程，用单调队列维护一个凸壳，降低复杂度
↑都是模板题↑
0x33 分治法
用线段树分治和cdq分治的思想来优化
P4095 [HEOI2013]Eden 的新背包问题 线段树分治+背包
P3120 [USACO15FEB]Cow Hopscotch G 类cdq分治
0x34 凸优化dp
wqs二分，给每个物品设置一个代价，从而找到最优解；但是注意函数必须满足凸性
CF739E Gosha is hunting wqs二分模板题
P4767 [IOI2000]邮局 wqs二分+决策单调性优化
0x35 矩阵加速
利用有结合律的矩阵乘法优化，当然矩阵乘法可以是广义的 这部分有部分题目与dp无关
P2579 [ZJOI2005]沼泽鳄鱼 矩阵快速幂+周期
P3216 [HNOI2011]数学作业 分段矩阵快速幂
P2886 [USACO07NOV]Cow Relays G 矩阵加速floyd
P3502 [POI2010]CHO-Hamsters 广义矩阵快速幂
0x36 动态dp
数据结构优化资瓷修改的dp
P4719 【模板】"动态 DP"&动态树分治 动态树上最大权独立集问题
P5024 保卫王国 动态树上最小权覆盖集问题
0x37 容斥原理
利用容斥优化dp
P5664 Emiya 家今天的饭 剪去无用状态+补集转化
P3349 [ZJOI2016]小星星 容斥+树形dp
CF348D Turtles 不相交路径的经典问题
0x38 子集 dp
又称 sos dp，利用一种方法将子集求和的复杂度从 降到
P6442 [COCI2011-2012#6] KOŠARE
均为容斥+sos dp
0x39 数据结构优化 dp
大多为线段树或者树状数组来优化 dp
P2605 [ZJOI2010]基站选址 线段树优化
P3287 [SCOI2014]方伯伯的玉米田 二维树状数组优化
0x3A 缩点
将双联通/强连通分量缩点再按拓扑序进行dp
P2656 采蘑菇 缩点 dp
P2515 [HAOI2010]软件安装 缩点+树上背包
0x4 数学问题
数论、期望+dp
这部分的子题单：「0x4 数学问题」
0x40 数论dp
说数论其实也就是一个质数
P6280 [USACO20OPEN]Exercise G 数论+dp
0x41 期望dp
数学期望的递推
P1654 OSU! 这两题均为 combo 的问题
P1850 换教室 期望dp&floyd
P4284 [SHOI2014]概率充电器 期望dp+换根