面向tg选手的DP练习题

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]连珠线

基环树DP

例题

P1453 城市环路
P2607 [ZJOI2008]骑士