之前的题单
本题单共 96 题
别考虑优化，推出方程直接AC
这部分的子题单：「0x1 暴力dp」
大多思维难度不高，也不需要啥优化，是基础的dp练手题
P1095 守望者的逃离 普通的线性dp，简单的分类讨论就好了
P1077 摆花 计数类dp，甚至不需要分类讨论
P3842 [TJOI2007]线段 线性dp，不过是要分类讨论
P1541 乌龟棋 暴力dp，很裸的题
P4059 [Code+#1]找爸爸 暴力dp，按照末尾空格分类
题目中大多有价值和体积，有些时候也要把题目转化成价值和体积的模型
P1833 樱花 多重背包模板
P1064 金明的预算方案 带有附带物品的背包问题，为树上背包打基础
P1941 飞扬的小鸟 背包建模
P2340 [USACO03FALL]Cow Exhibition G 巧妙的背包问题&分类讨论
状态大多为一个区间
P1880 [NOI1995]石子合并 简单的区间dp，配合断环成链的技巧就行啦
P3146 [USACO16OPEN]248 G 和上题类似，也是区间dp
P1063 能量项链 经典的区间dp
P4342 [IOI1998]Polygon 区间dp+断环成链
CF149D Coloring Brackets 区间dp，特殊的转移方式
UVA12991 Game Rooms 区间 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
对于数进行dp
P2657 [SCOI2009]windy数
P4124 [CQOI2016]手机号码
P2602 [ZJOI2010]数字计数
↑都是数位dp入门题↑
P2481 [SDOI2010]代码拍卖会 带有技巧性的数位dp
NOIp/csp 常考类型，最重要的dp
这部分的子题单：「0x2 树形dp」
没什么难度，入门级别的题目
P1352 没有上司的舞会 最大权独立集问题
P2016 战略游戏 最小权覆盖集问题
有依赖性的背包
P2014 [CTSC1997]选课 树上背包模板
P1273 有线电视网 树上背包经典题
P1272 重建道路 类似树上背包的树形dp
P3354 [IOI2005]Riv 河流 树上背包，也有更快的wqs二分做法
也叫换根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
P2495 [SDOI2011]消耗战 虚树dp模板题
P3233 [HNOI2014]世界树 虚树dp比较难的题
当 dp 状态只和深度有关的时候可以通过长链剖分优化到均摊
CF1009F Dominant Indices 长链剖分模板
P5904 [POI2014]HOT-Hotels 加强版 神仙 dp+长链剖分优化
P4292 [WC2010]重建计划 01 分数规划+线段树维护长链剖分
比较简单基础的题
P3174 [HAOI2009]毛毛虫
P3554 [POI2013]LUK-Triumphal arch
CF219D Choosing Capital for Treeland
P1131 [ZJOI2007]时态同步
P2052 [NOI2011]道路修建
P5658 括号树
稍微难一点的树dp
P4253 [SCOI2015]小凸玩密室
P4516 [JSOI2018]潜入行动
CF512D Fox And Travelling
CF543D Road Improvement
CF1146F Leaf Partition
CF1016F Road Projects
CF671D Roads in Yusland
有些时候暴力 dp 不再适用了，于是需要一些优化
这部分的子题单：「0x3 dp优化」
「一个人要是比你小，还比你强，那你就永远打不过他了」——单调队列
P2627 [USACO11OPEN]Mowing the Lawn G
P2569 [SCOI2010]股票交易
都比较模板，一般看完转移方程就能看出单调队列的影子
CF939F Cutlet 比较难的单调队列 dp
当一个转移方程中的价值函数满足四边形不等式时，那么这个方程的决策单调不降，这时就可以用二分+队列来维护
P1912 [NOI2009]诗人小G 决策单调性优化模板题
数形结合，适用于
P3195 [HNOI2008]玩具装箱
P4360 [CEOI2004]锯木厂选址
P3628 [APIO2010]特别行动队
CF311B Cats Transport
↑都是模板题↑
用线段树分治和cdq分治的思想来优化
P4095 [HEOI2013]Eden 的新背包问题 线段树分治+背包
P3120 [USACO15FEB]Cow Hopscotch G 类cdq分治
wqs二分，给每个物品设置一个代价，从而找到最优解；但是注意函数必须满足凸性
CF739E Gosha is hunting wqs二分模板题
P4767 [IOI2000]邮局 wqs二分+决策单调性优化
利用有结合律的矩阵乘法优化，当然矩阵乘法可以是广义的
这部分有部分题目与dp无关
P2579 [ZJOI2005]沼泽鳄鱼 矩阵快速幂+周期
P3216 [HNOI2011]数学作业 分段矩阵快速幂
P2886 [USACO07NOV]Cow Relays G 矩阵加速floyd
P3502 [POI2010]CHO-Hamsters 广义矩阵快速幂
数据结构优化资瓷修改的dp
P4719 【模板】"动态 DP"&动态树分治 动态树上最大权独立集问题
P5024 保卫王国 动态树上最小权覆盖集问题
利用容斥优化dp
P5664 Emiya 家今天的饭 剪去无用状态+补集转化
P3349 [ZJOI2016]小星星 容斥+树形dp
CF348D Turtles 不相交路径的经典问题
又称 sos dp，利用一种方法将子集求和的复杂度从
CF449D Jzzhu and Numbers
P6442 [COCI2011-2012#6] KOŠARE
CF383E Vowels 均为容斥+sos dp
大多为线段树或者树状数组来优化 dp
P2605 [ZJOI2010]基站选址 线段树优化
P3287 [SCOI2014]方伯伯的玉米田 二维树状数组优化
将双联通/强连通分量缩点再按拓扑序进行dp
P2656 采蘑菇 缩点 dp
P2515 [HAOI2010]软件安装 缩点+树上背包
数论、期望+dp
这部分的子题单：「0x4 数学问题」
说数论其实也就是一个质数
P6280 [USACO20OPEN]Exercise G 数论+dp
数学期望的递推
P1365 WJMZBMR打osu! / Easy
P1654 OSU! 这两题均为 combo 的问题
P1850 换教室 期望dp&floyd
P4284 [SHOI2014]概率充电器 期望dp+换根