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