DP综述
- 最优子结构：把原问题化到规模更小的问题后，原问题的最优解一定能从规模更小问题的最优解推出。
- 无后效性：如果在某个阶段上过程的状态已知，则从此阶段以后过程的发展变化仅与此阶段的状态有关，而与过程在此阶段以前的阶段所经历过的状态无关。
- 状态：类似搜索中所说的状态，就是怎么描述求解过程中的一个阶段。希望状态完整而不冗余地定义清楚子问题。
- 为什么动态规划和搜索相比更优秀？我们找出转移模式相同的、本质类似的那些状态，将其合并在一个新状态中，从而减少总的状态数量和转移路径数量。
解题套路
- 寻找子问题
- 设计状态描述
- 写出转移规则
- 确定边界
线性DP
往往用\(F_{i,s}\)表示区间\([1,i]\)在状态限制\(s\)下的最优解。
例题
P4310 绝世好题
P1944 最长括号匹配
P1772 [ZJOI2006]物流运输
背包DP
- 01背包
- 完全背包
- 多重背包
- 二进制拆分
- 斜率优化
- 分组背包
- 树形背包
例题
P4158 [SCOI2009]粉刷匠
P1284 三角形牧场
P1156 垃圾陷阱
P1941 飞扬的小鸟
P1282 多米诺骨牌
P5322 [BJOI2019]排兵布阵
P2224 [HNOI2001]产品加工
P3188 [HNOI2007]梦幻岛宝珠
P4141 消失之物
P2340 [USACO03FALL]Cow Exhibition G
P4095 [HEOI2013]Eden的新背包问题
P2851 [USACO06DEC]The Fewest Coins G
区间DP
依照子区间来定义子问题。
大区间的求解依赖于其内部小区间的求解。
往往用\(F_{l,r,s}\)表示区间\([l,r]\)在状态限制\(s\)下的最优解。
按照区间长度从小到大依次求解。
单点构成的区间或空区间无需递归。
TIPS ：尝试下面三种转移思路
- \(F_{l,r,s} = max{F_{l+1,r,s'},F_{l,r-1,s'}}\)
- \(F_{l,r,s} = max_{l\leq k<r}{f(F_{l,k,s'},F_{k+1,r,s'})}\)
- \(F_{l,r,s} = max_{l\leq k\leq r}{f(F_{l,k,s'},F_{k,r,s'})}\)
例题
P1040 加分二叉树
P2890 [USACO07OPEN]Cheapest Palindrome G
P4170 [CQOI2007]涂色
UVA1437 String painter
CF149D Coloring Brackets
P5851 [USACO19DEC]Greedy Pie Eaters P
UVA1629 切蛋糕 Cake slicing
P3205 [HNOI2010]合唱队
树形DP
问题定义在树形结构上，依照子树设定子问题。
常常用\(F_{u,s}\)表示子树\(u\)在状态限制\(s\)下的最优解。
先递归求解子树的答案，再计算当前结点答案。
普通树形DP
例题
P1122 最大子树和
P1352 没有上司的舞会
P4084 [USACO17DEC]Barn Painting G
P2016 战略游戏
P2458 [SDOI2006]保安站岗
P3621 [APIO2007]风铃
P4099 [HEOI2013]SAO
P3174 [HAOI2009]毛毛虫
P3237 [HNOI2014]米特运输
树形依赖背包
要选取一个结点上的物品，需要选取其父结点的物品。
- 朴素写法：枚举子树分配体积（01背包用点对数量分析）
- 2009年国家集训队论文 徐持衡《浅谈几类背包题》
- 借助DFS序拍平成线性结构
DFS序为\(i\)的点子树大小为\(S_i\)，体积为\(W_i\),价值为\(V_i\),\(F_{i,j}=\max\{F_{i+S_i,j},F_{i+1,j-W_i}+V_i\}\) (i从大到小倒序枚举)
例题
P1273 有线电视网
P2014 [CTSC1997]选课
P2015 二叉苹果树
P3177 [HAOI2015]树上染色
P3354 [IOI2005]Riv 河流
P1270 “访问”美术馆
P4322 [JSOI2016]最佳团体
P1272 重建道路
P4037 [JSOI2008]魔兽地图
换根
- 先以1为根结点，求出\(F_u\)表示\(u\)子树的最优解
- 考虑将根结点换到1的邻点2上，只有1和2两个结点的相对关系发生变化，快速地计算出新的\(F_1\)和\(F_2\)
- 继续换根直到尝试过以每个点为根结点
- 回溯操作就是递归操作的逆
例题
P3478 [POI2008]STA-Station
P2986 [USACO10MAR]Great Cow Gathering G
P3047 [USACO12FEB]Nearby Cows G
P5898 [COCI 2015]Kamp
P3647 [APIO2014]连珠线